perm filename V2F.IN[1,DEK] blob sn#285509 filedate 1977-05-29 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	folio 223 galley 1E
C00022 00003	folio 229 galley 2E NOTE:Middle and end of this galley couldn't be read.
C00034 00004	folio 234 galley 1
C00051 00005	folio 237 galley 2
C00070 00006	folio 241 galley 3
C00091 00007	folio 245 galley 4
C00107 00008	folio 249 galley 5
C00126 00009	folio 254 galley 6
C00150 00010	folio 259 galley 7
C00163 ENDMK
C⊗;
folio 223 galley 1E
    0  {U0}{H10L12M29}58320#Computer Programming!(Knuth/A-W)!f. 
    2  223!g. 1E!ch 3|'{H9L11}|π|≡3|≡8|≡.|9|4[|εM|*/|↔M|↔m|\] 
    6  |π(A. N. Kolmogorov.) Given |εN, n |πand |ε|≤e 
   14  |πwhat is the smallest number of algorithms in 
   22  a set |≡A such that no |ε(n,|4|≤e)-|πrandom binary 
   30  sequences of length |εN |πexist with respect 
   37  to |≡A? (If exact formulas cannot be given, can 
   46  asymptotic formulas be found? The point of this 
   54  problem is to discover how close the bound (35) 
   63  comes to being ``best possible.'')|'{A3}|≡3|≡9|≡.|9|4[|εHM|*/
   68  |↔M|↔C|\] (|πW. M. Schmidt.) Let |εU|βn |πbe 
   75  a [0,|41) sequence, and let |ε|≤n|βn(u) |πbe 
   82  the number of nonnegative integers |εj|4|¬E|4n 
   88  |πsuch that |ε0|4|¬W|4U|βj|4|¬E|4u. |πProve that 
   93  there is a positive constant |εc |πsuch that, 
  101  for any |εN |πand for any [0,|41) sequence |↔b|εU|βn|↔v, 
  110  |πwe have|'{A9}|¬G|ε|≤n|βn(u)|4α_↓|4un|¬G|4|¬Q|4c|4|πlog|4|ε
  112  N|;{A9}|πfor some |εn |πand |εu |πwith |ε0|4|¬E|4n|4|¬W|4N, 
  120  0|4|¬E|4u|¬W|41. |π(In other words, no [0,|41) 
  126  sequence can be |εtoo |πequidistributed.)|'{A3}|≡4|≡1|≡.|9|4
  131  [|ε|*/|↔O|↔o|\] |π(I. J. Good.) Can a valid table 
  139  of random digits contain just one misprint?|'
  146  {A24}{H10L12M29}|∨3|∨.|∨6|∨.|9|4|∨S|∨U|∨M|∨M|∨A|∨R|∨Y|'
  147  {A12}We have covered a fairly large number of 
  155  topics in this chapter: how to generate random 
  163  numbers, how to test them, how to modify them 
  172  in applications, and how to derive theoretical 
  179  facts about them. Perhaps the main question in 
  187  many raders' minds will be, ``What is the result 
  196  of all this theory? What is a simple, virtuous, 
  205  random-number generator I can use in my programs 
  213  in order to have a reliable source of random 
  222  numbers?''|'!|4|4|4|4The detailed investigations 
  226  in this chapter suggest that the following procedure 
  234  gives the ``nicest'' and ``simplest'' random-number 
  240  generator for the machine language of must computers: 
  248  At the beginning of the program, set an integer 
  257  variable |εX |πto some value |εX|β0. |πThis variable 
  265  |εX |πis to be used only for the purpose of random-number 
  276  generation. Whenever a new random number is required 
  284  by the program, set|'{A9}|εX|4|¬L|4(aX|4α+↓|4c)|πmod|4|εm|J!
  288  (1)|;{A9}|πand use the new value of |εX |πas 
  297  the random value. It is necessary to choose |εX|β0, 
  306  a, c, |πand |εm |πproperly, and to use the random 
  316  numbers widely, according to the following principles:|'
  323  !|4|4|4|4i)|9|4The ``seed'' number |εX|β0 |πmay 
  328  be chosen arbitrarily. If the program is run 
  336  several times and a di=erent source of random 
  344  numbers is desired each time, set |εX|β0 |πto 
  352  the last value attained by |εX |πon the preceding 
  361  run; or (if more convenient) set |εX|β0 |πto 
  369  the current date and time. If the program may 
  378  need to be rerun later with the |εsame |πrandom 
  387  numbers (e.g., when debugging), be sure to print 
  395  out |εX|β0 |πif it isn't otherwise known.|'!|4|4|4|4ii)|9|4T
  402  he number |εm |πshould be large, say at least 
  411  2|g3|g0. It may conveniently be taken as the 
  419  computer's word size, since this makes the computation 
  427  of |ε(aX|4α+↓|4c)|πmod|4|πm quite e∃cient. Section 
  432  3.2.1.1 discusses the choice of |εm |πin more 
  440  detail. The computation of |ε(aX|4α+↓|4c)|πmod 
  445  |εm |πmust be done |εexactly, |πwith no roundo= 
  453  error.|'!|4|4|4|4iii)|9|4If |εm |πis a power 
  459  of 2 (i.e., if a binary computer is being used), 
  469  pick |εa |πso that |εa |πmod 8|4α=↓|45. If |εm 
  478  |πis a power of 10 (i.e., if a decimal computer 
  488  is being used), choose |εa |πso that |εa|4|πmod|4200|4α=↓|42
  495  1. This choice of |εa |πtogether with the choice 
  504  of |εc |πgiven below ensures that the random-number 
  512  generator will produce all |εm |πdi=erent possible 
  519  values of |εX |πbefore it starts to repeat (see 
  528  Section 3.2.1.2) and ensures high ``potency'' 
  534  (see Section 3.2.1.3).|'!|4|4|4|4iv)|9|4The multiplier 
  539  |εa |πshould preferably be chosen between .01|εm 
  546  |πand .99|εm, |πand its binary or decimal figits 
  554  should |εnot |πhave a simple, regular pattern. 
  561  By choosing some haphazard constant like |εa|4α=↓|4314159262
  567  1 |π(which satis_es both of the conditions in 
  575  (iii){H12}){H10}, one almost always obtains a 
  581  reasonably good multiplier. Further testing should 
  587  of course be done if the random-number generator 
  595  is to be used extensively; for example, there 
  603  should be no large quotients when Euclid's algorithm 
  611  is used to _nd the gcd of |εa |πand |εm |π(see 
  622  Section 3.3.3). The multiplier should pass the 
  629  spectral test (Section 3.3.4) and several tests 
  636  of Section 3.3.2 before it is considered to have 
  645  a truly clean bill of health.|'!|4|4|4|4v)|9|4The 
  652  value of |εc |πis immaterial when |εa |πis a 
  661  good multiplier, except that |εc |πmust have 
  668  no factor in common with |εm. |πThus we may choose 
  678  |εc|4α=↓|41 |πor |εc|4α=↓|4a.|'|π!|4|4|4|4vi)|9|4The 
  682  least signi_cant (right-hand) digits of |εX |πare 
  689  not very random, so decisions based on the number 
  698  |εX |πshould always be primarily in⊗uenced by 
  705  the most signi_cant digits. It is generally best 
  713  to think of |εX |πas a random fraction |εX/m 
  722  |πbetween 0 and 1, that is, to visualize |εX 
  731  |πwith a decimal point at its left, than to regard 
  741  |εX |πas a random integer between 0 and |εm|4α_↓|41. 
  750  |πTo compute a random integer between 0 and |εk|4α_↓|41, 
  759  |πone should multiply by |εk |πand truncate the 
  767  result (see the beginning of Section 3.4.2).|'
  774  !|4|4|4|4vii)|9|4An important limitation on the 
  779  randomness of sequence (1) is discussed in Section 
  787  3.3.4, where it is shown that the ``accuracy'' 
  795  in |εt |πdimensions will be only about one part 
  804  in |ε|¬H|v4m|). |πMonte Carlo applications requiring 
  810  higher resolution can improve the randomness 
  816  by employing techniques discussed in Section 
  822  3.2.2.|'!|4|4|4|4The above comments apply primarily 
  828  to machine-language coding. In higher-level programming 
  834  languages, we are often unable to use such machine-dependent
  842   features as integer arithmetic modulo the word 
  850  size, and careful compilers will not allow us 
  858  to compute the product of two large integers. 
  866  Another technique which we migh call the |εsubtractive 
  874  method |π(exercise 3.2.223) can be used to provide 
  882  a ``portable'' random number generator which 
  888  is e∃ciently describable in any higher-level 
  894  programming language, since it makes use only 
  901  of integer arithmetic between |→α_↓10|g9 and 
  907  10|g9. Here is how the subtractive method light 
  915  be coded in FORTRAN, as a subroutine which delivers 
  924  an array of 55 random integers at once:|'{A9}{H9L11M29}!!|9|
  932  4|¬f|¬u|¬n|¬c|¬t|¬i|¬o|¬n |¬i|¬r|¬n|¬5|¬5|≤#|¬i|¬a|≤&|'
  934  !!|4|9|¬d|¬i|¬m|¬e|¬n|¬s|¬i|¬o|¬n |¬i|¬a|≤#|¬1|≤&|'
  936  |¬c!!|1|1|¬a|¬s|¬s|¬u|¬m|¬i|¬n|¬g |¬t|¬h|¬a|¬t 
  938  |¬i|¬a|≤#|¬1|≤&|¬,|4.|4.|4.|4.|4|¬,|4|¬i|¬a|≤#|¬5|¬5|≤& 
  939  |¬h|¬a|¬v|¬e |¬b|¬e|¬e|¬n |¬s|¬e|¬t |¬u|¬p |¬p|¬r|¬o|¬p|¬e|¬
  943  r|¬l|¬y|'|¬c!!|1|1|¬t|¬h|¬i|¬s |¬s|¬u|¬b|¬r|¬o|¬u|¬t|¬i|¬n|¬
  945  e |¬r|¬e|¬s|¬e|¬t|¬s |¬t|¬h|¬e |¬i|¬a |¬a|¬r|¬r|¬a|¬y 
  950  |¬t|¬o |¬t|¬h|¬e |¬n|¬e|¬x|¬t |¬5|¬5 |¬n|¬u|¬m|¬b|¬e|¬r|¬s|'
  955  |¬c!!|1|1|¬o|¬f |¬a |¬p|¬s|¬e|¬u|¬d|¬o-|¬r|¬a|¬n|¬d|¬o|¬m 
  958  |¬s|¬e|¬q|¬u|¬e|¬n|¬c|¬e|¬, |¬a|¬n|¬d |¬r|¬e|¬t|¬u|¬r|¬n|¬s 
  961  |¬t|¬h|¬e |¬v|¬a|¬l|¬u|¬e |¬1.|'!!|4|9|¬d|¬o 
  965  |¬1 |¬i|≤$|¬1|¬, |¬2|¬4|'!!|4|9!|¬j|≤$|¬i|¬a|≤#|¬i|≤%|¬3|¬1|
  968  ≤&|'!!|4|9!|¬i|¬f |≤#|¬j.|¬l|¬t.|¬o|≤& |¬j|≤$|¬j|≤%|¬1|¬0|¬0
  971  |¬0|¬0|¬0|¬0|¬0|¬0|¬0|'|4|4|4|4|4|¬1!!|¬i|¬a|≤#|¬i|≤&|≤$|¬j|
  972  '!!|4|9|¬d|¬o |¬2 |¬i|≤$|¬2|¬5|¬, |¬5|¬5|'!!!|9|4|¬j|≤$|¬i|¬
  977  a|≤#|¬i|≤#|≤*/|¬i|¬a|≤#|¬i|≤*/|¬2|¬4|≤&|'!!!|4|9|¬i|¬f 
  979  |≤#|¬j .|¬l|¬t. |¬0|≤& |¬j|≤$|¬j|≤%|¬1|¬0|¬0|¬0|¬0|¬0|¬0|¬0|
  982  ¬0|¬0|'|4|4|4|4|4|¬2!!|¬i|¬a|≤#|¬i|≤&|≤$|¬j|'
  984  !!|9|4|¬i|¬r|¬n|¬5|¬5|≤$|¬1|'!!|9|4|¬r|¬e|¬t|¬u|¬r|¬n|'
  986  !!|9|4|¬e|¬n|¬d|'{A9}{H10L12M29}To use these 
  990  numbers in a FORTRAN program, let |¬j|¬r|¬a|¬n|¬d 
  997  be an auxiliary integer variable; we may obtain 
 1005  the next random number |¬u (as a fraction between 
 1014  0 and 1) by writing the following three statements:|'
 1023  {A9}{H9L11}!!|9|4|¬j|¬r|¬a|¬n|¬d|≤$|¬j|¬r|¬a|¬n|¬d|≤%|¬1|'
 1024  !!|9|4|¬i|¬f |≤#|¬j|¬r|¬a|¬n|¬d .|¬g|¬t. |¬5|¬5|≤& 
 1028  |¬j|¬r|¬a|¬n|¬d|≤$|¬i|¬r|¬n|¬5|¬5|≤#|¬i|¬a|≤&|'
 1029  !!|9|4|¬u|≤$|¬f|¬l|¬o|¬a|¬t|≤#|¬i|¬a|≤#|¬j|¬r|¬a|¬n|¬d|≤&|≤&
 1029  !|¬1.|¬0|¬e|≤*/|¬9|'{A9}{H10L12M29}At the beginning 
 1033  of our program we write ``|¬d|¬i|¬m|¬e|¬n|¬s|¬i|¬o|¬n 
 1039  |¬i|¬a|≤#|¬5|¬5|≤&'' and ``|¬j|¬r|¬a|¬n|¬d|≤$|¬5|¬5'' 
 1042  and we must also initialize the |¬i|¬a array. 
 1050  Appropriate initialization can be done by calling 
 1057  the following subroutine with |¬i|¬x set to any 
 1065  integer value (selected like |εX|β0 |πin rule 
 1072  (i) above, preferably large):|'{A9}{H9L11}!!|9|4|¬s|¬u|¬b|¬r
 1076  |¬o|¬u|¬t|¬i|¬n|¬e |¬i|¬n|¬5|¬5|≤#|¬i|¬a|¬,|¬i|¬x|≤&|'
 1078  |¬c!!|1|1|¬t|¬h|¬i|¬s |¬s|¬u|¬b|¬r|¬o|¬u|¬t|¬i|¬n|¬e 
 1080  |¬s|¬e|¬t|¬s |¬i|¬a|≤#|¬1|≤&|4.|4.|4.|4|¬i|¬a|≤#|¬5|¬5|≤& 
 1082  |¬t|¬o |¬s|¬t|¬a|¬r|¬t|¬i|¬n|¬g |¬v|¬a|¬l|¬u|¬e|¬s|'
 1085  |¬c!!|1|1|¬s|¬u|¬i|¬t|¬a|¬b|¬l|¬e |¬f|¬o|¬r |¬l|¬a|¬t|¬e|¬r 
 1088  |¬c|¬a|¬l|¬l|¬s |¬o|¬n |¬i|¬r|¬n|¬5|¬5|≤#|¬i|¬a|≤&.|'
 1091  |¬c!!|1|1|¬i|¬x |¬i|¬s |¬a|¬n|¬y |¬i|¬n|¬t|¬e|¬g|¬e|¬r 
 1095  ``|¬s|¬e|¬e|¬d'' |¬v|¬a|¬l|¬u|¬e |¬b|¬e|¬t|¬w|¬e|¬e|¬n 
 1098  |¬0 |¬a|¬n|¬d |¬1|¬0|¬0|¬0|¬0|¬0|¬0|¬0|¬0|¬0.|'
 1101  !!|9|4|¬i|¬a|≤#|¬5|¬5|≤&|≤$|¬i|¬x|'!!|9|4|¬j|≤$|¬i|¬x|'
 1103  !!|9|4|¬k|≤$|¬1|'!!|9|4|¬d|¬o |¬1 |¬i|≤$|¬1|¬, 
 1107  |¬5|¬4|'!!!|9|4|¬i|¬i|≤$|¬m|¬o|¬d|≤#|¬2|¬1{J3}|≤⊃|¬i|¬, 
 1109  |¬5|¬5|≤&|'!!!|9|4|¬i|¬a|≤#|¬i|¬i|≤&|≤$|¬k|'!!!|9|4|¬k|≤$|¬j
 1111  |≤*/|¬k|'!!!|9|4|¬i|¬f|≤$|≤#|¬k .|¬l|¬t. |¬0|≤&|¬k|≤$|¬k|≤%|¬
 1114  1|¬0|¬0|¬0|¬0|¬0|¬0|¬0|¬0|¬0|'!!!|9|4|¬j|≤$|¬i|¬a|≤#|¬i|¬i|≤
 1115  &|'|4|4|4|4|4|¬1!|¬c|¬o|¬n|¬t|¬i|¬n|¬u|¬e|'!!|9|4|¬r|¬e|¬t|¬
 1117  u|¬r|¬n|'!!|9|4|¬e|¬n|¬d|'{A9}{H10L12M29}(This 
 1120  subroutine computes a Fibonacci-like sequence; 
 1125  multiplication of indices by 21 spreads the values 
 1133  around so as to alleviate initial nonrandomness 
 1140  problems such as those in exercise 3.2.2<2. Note 
 1148  that 2|g2|g9|4|¬W|410|g9|4|¬W|42|g3|g0; any large 
 1152  even number may actually be substituted for 10|g9 
 1160  in these rountines, if a corresponding change 
 1167  is made in the computation of the random fraction 
 1176  |¬u. The numbers (24,|455) may be replaced by 
 1184  any pair of values |ε(j, k) |πin Table 3.2.2<1, 
 1193  for |εk|4|¬R|450; |πthe constants 31, 25, 54, 
 1200  21 should then be replaced by |εk|4α_↓|4j, j|4α+↓|41, 
 1208  k|4α_↓|41, |πand |εd |πrespectively, where |εd 
 1214  |πis relatively prime to |εk |πand |εd|4|¬V|4k/|≤f|g2.)|'
 1221  |π!|4|4|4|4Although a great deal is known about 
 1228  linear congruential sequences like (1), very 
 1234  little has yet been proved about the randomness 
 1242  properties of the subtractive method. Both approaches 
 1249  seem to be reliable in practice.|'!|4|4|4|4Unfortunately, 
 1256  quite a bit of published material in existence 
 1264  at the time this chapter was written recommends 
 1272  the use of generators which violate the suggestion 
 1280  above; and the most common generator in actual 
 1288  use, |¬r|¬a|¬n|¬d|¬u, is really horrible (cf. 
 1294  Section 3.3.4). The authors of many contributions 
 1301  to the science of random-number generation were 
 1308  unaware that particular methods they were advocating 
 1315  would prove to be inadequate.|'|H*?*?{U0}{H10L12M29}58320#Comp
folio 229 galley 2E NOTE:Middle and end of this galley couldn't be read.
 1320  uter Programming!(Knuth/A.-W)!f. 229!ch. 3!g. 
 1324  2E|'{A12}!|4|4|4|4Excellent bibliographies of 
 1328  the pre-1972 literature on random-number generation 
 1334  have been compiled by Richard E. Nance and Claude 
 1343  Overstreet, Jr., |εComputing Reviews |≡1|≡3 |π(1972), 
 1349  495<508, and by E. R. Sowey, |εInternational 
 1356  Stat. Review |≡4|≡0 |π(1972), 355<371. For further 
 1363  study, especially with respect to |εa priori 
 1370  |πtheoretical tests, see the book |εUniform Random 
 1377  Numbers |πby U. Dieter and J. H. Ahrens (New 
 1386  York: Wiley, 1975).|'!|4|4|4|4For a detailed 
 1392  study of the use of random numbers in numerical 
 1401  analysis, see J. M. Hammersley and D. C. Handscomb, 
 1410  |εMonte Carlo Methods (|πLondon: Methuen, 1964). 
 1416  This book shows that many numerical methods are 
 1424  enhanced by using numbers which are ``quasirandom,'' 
 1431  designed speci_cally for a certain purpose (not 
 1438  necessarily satisfying the statistical tests 
 1443  we have discussed).|'{A24}|∨E|∨X|∨E|∨R|∨C|∨I|∨S|∨E|∨S|'
 1447  {A12}{H9L11M29}|9|1|≡1|≡.|9|4[|ε|*/|↔P|↔O|\] |πWrite 
 1449  a |¬m|¬i|¬x subroutine with the following characteristics, 
 1456  using method (1):|'{A9}|h|π!!|1|1Entry|4|1conditions:!!|∂oip
 1459  lokoikju|E|n|'!!|1|1Calling|4|1sequence:|L|¬j|¬m|¬p!|¬r|¬a|¬
 1460  n|¬d|¬i>!!|1|1Entry|4|1conditions:!!rA|4α=↓|4|εk, 
 1462  |πa positive integer|4|¬W|45000|'!!|1|1Exit|4|1conditions:|L
 1465  rA|4|¬L|4a random integer |εY, 1|4|¬E|4Y|4|¬E|4k, 
 1470  |πwith each integer>|Lequally probable; rX|4α=↓|4?; 
 1476  over⊗ow o=.|'{A3}|9|1|≡2|≡.|9|4[|ε|*/|↔P|↔O|\] 
 1479  |πSome people have been afraid computers will 
 1486  someday take over the world; but they are reassured 
 1495  by the statement that a machine cannot do anything 
 1504  really new, since it is only obeying the commands 
 1513  of its master, the programmer. Lady Lovelace 
 1520  wrote in 1844, ``The Analytical Engine has no 
 1528  pretensions to |εoriginate |πanything. It can 
 1534  do |εwhatever we know how to ordr it |πto perform.'' 
 1544  Her statement has been further elaborated by 
 1551  many philosophers. |πDiscuss this topic, with 
 1557  random-number generators in mind.|'{A3}|9|1|≡3|≡.|9|4[|ε|*/|↔
 1561  L|↔P|\] (A dice game.) |πWrite a program that 
 1569  simulates a roll of two dice, each of which takes 
 1579  on the values 1, 2,|4.|4.|4.|4, 6 with equal 
 1587  probability. If the total is 7 or 11 on the _rst 
 1598  roll, the game is won; a total of 2, 3, or 12 
 1610  loses; and on any other total, call that total 
 1619  the ``point'' and continue rolling dice until 
 1626  either a 7 occurs (a loss) or the point occurs 
 1636  again (a win).|'!!|1|1Play ten games. The result 
 1644  of each roll of the dice should be printed in 
 1654  the form |εmn, |πwhere |εm |πand |εn |πare the 
 1663  contents of the two dice, followed by some appropriate 
 1672  comment (like ``snake eyes'' or ``little Joe'' 
 1679  or ``the hard way,'' etc.)|'{A3}|9|1|≡4|≡.|9|4[|ε|*/|↔M|↔c|\]
 1684   (Solitaire or patience.) |πSome people spend 
 1691  a lot of valuable time playing card games of 
 1700  solitaire, and perhaps automation will make an 
 1707  important inroad in this area. Write a program 
 1715  that (a) shu+es a simulated deck of cards; (b) 
 1724  plays some common game of solitaire based on 
 1732  the order of the cards in the deck; (c) prints 
 1742  out the result of the game, i.e., how close the 
 1752  program came to winning. Several games should 
 1759  be played. The program might be set up to ``cheat'' 
 1769  upon request.|'{A3}|9|1|≡5|≡.|9|4[|ε|*/|↔M|↔o|\] 
 1772  (Creative writing by computer.) |πA television 
 1778  program entitled ``The Thinking Machine,'' broadcast 
 1784  by the CBS television network on October 26, 
 1792  1960, featured (among other things) two Western-style 
 1799  playlets which were written by a computer program. 
 1807  Here are the two scipts as they were printed 
 1816  by the computer:|'{A9}|E|'|}|O{H8L9M29}|*/Saga 
 1821  |9|4|\1.|9|4(The gun is in the right hand; the 
 1829  money is in the left hand; the glass is on the 
 1840  table; the bottle is on the table; the holster 
 1849  is on the robber; the sheri='s gun is in the 
 1859  sheri='s right hand; the sheri='s holster is 
 1866  on the sheri=.)|'{I3.5H}ROBBER;|9|4(The robber 
 1871  is at the window.) Go to door; open door; go 
 1881  thru door; close door; go to corner; put money 
 1890  down at corner; go to table; put gun on table; 
 1900  sit and _dgit; sit at table; pick up glass with 
 1910  right hand (empty); put glass on table; pick 
 1918  up bottle with right hand; pour; put bottle on 
 1927  table; pick up glass with right hand; take a 
 1936  drink from glass; put glass on table;{A3}SHERIFF:|9|4(The 
 1943  sheri= is at the window.) See robber; (robber 
 1951  sees sheri=); go to door.|'{A3}ROBBER:|9|4Put 
 1957  glass on table; pick up gun with right hand; 
 1966  check gun.|'{A3}SHERIFF:|9|4Wait; open door; 
 1971  see robber; (robber sees sheri=); go thru door.|'
 1979  {A3}ROBBER:|9|4Go to window; aim; _re; SHERIFF 
 1985  NICKED.|'{A3}SHERIFF:|9|4Go to window; aim; _re; 
 1991  MISSED; go to door; go to window.|'{A3}ROBBER:|9|4Go 
 1999  to door; aim; aim.|'{A3}Sheriff:|9|4Aim; _re; 
 2005  MISSED.|'{A3}ROBBER:|9|4Fire; SHERIFF NICKED.|'
 2009  {A3}SHERIFF:|9|4Go to door; aim; _re; MISSED; 
 2015  go thru door; aim.|'{A3}ROBBER:|9|4Aim; _re; 
 2021  MISSED; aim; _re; MISSED.|'{A3}SHERIFF:|9|4Fire; 
 2026  MISSEDROBBER:|9|4Drop gun; robber dies.|'|*/Saga 
 2031  |9|4|\2.|9|4(The gun is in the right hand; the 
 2039  money is in the left hand; the glass is on the 
 2050  table; the bottle is on the table; the holster 
 2059  is on the robber; the sheri='s gun is in the 
 2069  sheri='s right hand; the sheri='s holster is 
 2076  on the sheri=.)|'{A3}{I3.5H}ROBBER:|9|4(The robber 
 2081  is at the window.) Go to door; open door; go 
 2091  thru door; close door; go to corner; put money 
 2100  down at corner; go to window; put gun down at 
 2110  window; lean on window and look; lean on window 
 2119  and look; go to corner; count money; go to table; 
 2129  pick up glass with right hand (empty); take glass 
 2138  from right hand with left hand; pick up bottle 
 2147  with right hand; pour; put bottle on table; take 
 2156  glass from left hand with right hand; take a 
 2165  drink from glass; put glass on table; pick up 
 2174  bottle with right hand; pour; go to corner; put 
 2183  bottle down at corner; to to window; pick up 
 2192  gun with right hand; check gun; put gun in holster; 
 2202  go to table; pick up glass with right hand; take 
 2212  a dr*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
 2213  
folio 234 galley 1
    0  {U0}{H10L12M29}|π58320#Computer Programming!(Knuth/Addison-W
    1  esley)!f. 234!ch. 4!g. 1|'{A12}{H11L12}|!C|1|1|!H|4|!A|2|!P|
    5  2|!T|2|!E|2|!R|9|1|!F|2|!O|2|!U|2|!R|'{A46}{H20L20}|∨A|∨R|∨I
    6  |∨T|∨H|∨M|∨E|∨T|∨I|∨C|?{A12}{H8L11}|E|'|}|O{H8L11M29}|*/Seein
    8  g there is nothing (right well beloved Students 
   16  in the Mathematickes)|?that is so troublesome 
   23  to Mathematicall practise, nor that doth more 
   30  molest|?and hinder Calculators, then the Multiplications, 
   37  Divisions, square and|?cubical Extractions of 
   43  great numbers, which besides the tediuus expence 
   50  of|?time are for the most part subject to many 
   60  slippery errors. I began therefore|?to consider 
   67  in my minde, by what certaine and ready Art I 
   77  might|?remove those hindrances.|?{A6}|\#JOHN 
   82  NAPIER (1614)|?{A11}|*/I do hate sums. There is 
   90  no greater mistake than to call arithmetic an 
   98  exact|?science. There are|4.|4.|4.|4hidden laws 
  103  of number which it requires a mind|?like mine 
  112  to perceive. For instance, if you add a sum from 
  122  the bottom up,|?and then again from the top down, 
  132  the result is always di=erent.|?{A6}|\#MRS. LA 
  139  TOUCHE (19th century)|?{A11}|*/I cannot conceive 
  145  that anybody will require multiplications at 
  151  the rate|?of 40,000, or even 4,000 per hour; 
  160  such a revolutionary change as the|?octonary 
  167  scale should not be imposed upon mankind in general|?
  176  for the sake of a few individuals.|?{A6}|\#F. 
  184  H. WALES (1936)|?{A38}|!|E|'|{{H10L12M29}|πThe 
  189  chief purpose of this chapter is to make a careful 
  199  study of the four basic processes of arithmetic: 
  207  addition, subtraction, multiplication, and division. 
  212  Many people regard arithmetic as a trivial thing 
  220  which children learn and computers do, but we 
  228  will see that artihmetic is an intriguing topic 
  236  with many interesting facets. It is important 
  243  to make a thorough study of e∃cient methods for 
  252  calculating with numbers, since arithmetic underlies 
  258  so many computer applications.|'!|9|7Arithmetic 
  263  is, in fact, a lively subject which has played 
  272  an important part in the history of the world, 
  281  and it still is undergoing rapid development. 
  288  In this chapter, we will analyze algorithms for 
  296  doing arithmetic operations on many types of 
  303  quantities, such as ``⊗oating-point'' numbers, 
  308  extremely large numbers, fractions (rational 
  313  numbers), polynomials, and power series; and 
  319  we will also discuss related topics such as radix 
  328  conversion, factoring of numbers, and the evaluation 
  335  of polynomials.|'{A24}|∨4|∨.|∨1|∨.|9|∨P|∨O|∨S|∨I|∨T|∨I|∨O|∨N
  337  |∨A|∨L|9|∨N|∨U|∨M|∨B|∨E|∨R|9|∨S|∨Y|∨S|∨T|∨E|∨M|∨S|'
  338  {A12}The way we do arithmetic is intimately related 
  346  to the way we represent the numbers we deal with, 
  356  so it is appropriate to begin our study of arithmetic 
  366  with a discussion of the principal means for 
  374  representing numbers.|'!|9|7Positional notation 
  378  using base |εb |π(alternatively called |εradix 
  384  b) |πis de_ned by the rule|'{A9}|ε(.|4.|4.|4a|β3a|β2a|β1a|β0
  390  .a|βα_↓|β1a|βα_↓|β2|4.|4.|4.)|βb|'α=↓|4|¬O|4|¬O|4|¬O|4α+↓|4a
  391  |β3b|g3|4α+↓|4a|β2b|g2|4α+↓|4a|β1b|g1|4α+↓|4a|β0|4α+↓|4a|βα_
  391  ↓|β1b|gα_↓|g1|4α+↓|4a|βα_↓|β2b|gα_↓|g2|4α+↓|4|¬O|4|¬O|4|¬O|4
  391  ;!(1)|?{A9}|πfor example, (520.3)|β6|4α=↓|45|4|¬O|46|g2|4α+↓
  394  |42|4|¬O|46|g1|4α+↓|40|4α+↓|43|4|¬O|46|gα_↓|g1|4α=↓|4192|f1|
  394  d32|). Our conventional decimal number system 
  400  is, of course, the special case when |εb |πis 
  409  ten, and when the |εa'|πs are chosen from the 
  418  ``decimal digits'' 0, 1, 2, 3, 4, 5, 6, 7, 8, 
  429  9; in this case the subscript |εb |πin (1) may 
  439  be omitted.|'!|9|6The simplest generalizations 
  444  of the decimal number dystem are obtained when 
  452  we take |εb |πto be an integer greater than 1 
  462  and when we require the |εa'|πs to be integers 
  471  in the range 0|4|¬E|4|εa|βk|4|¬W|4b. |πThis gives 
  477  us the standard binary |ε(b|4α=↓|42), |πternary 
  483  |ε(b|4α=↓|43), |πquaternary |ε(b|4α=↓|44), |πquinary 
  487  |ε(b|4α=↓|45), . . . |πnumber systems. In general, 
  495  we could take |εb |πto be any number, and we 
  505  could choose the |εa'|πs from any speci_ed set 
  513  of numbers; this leads to some interesting situations, 
  521  as we shall see.|'!|9|7The dot which appears 
  529  between |εa|β0 |πand |εa|βα_↓|β1 |πin (1) is 
  536  called the |εradix point. |π(When |εb|4α=↓|410, 
  542  |πit is also called the decimal point, and when 
  551  |εb|4α=↓|42, |πit is sometimes called the binary 
  558  point, etc.) Europeans often use a comma instead 
  566  of a dot to denote the radix point; Englishmen 
  575  often use a raised dot.|'!|9|7The |εa'|πs in 
  583  (1) are called the |εdigits |πof the representation. 
  591  A digit |εa|βk |πfor large |εk |πis often said 
  600  to be ``more signi_cant'' than the digits |εa|βk 
  608  |πfor small |εk; |πaccordingly, the leftmost 
  614  or ``leading'' digit is referred to as the |εmost 
  623  signi⊂cant digit. |πIn the standard binary system 
  630  the binary digits are often called |εbits. |πIn 
  638  the standard hexadecimal system (radix sixteen) 
  644  the hexadecimal digits zero through _fteen are 
  651  usually denoted by|'{A9}|¬0|¬,|¬1|¬,|¬2|¬,|¬3|¬,|¬4|¬,|¬5|¬,
  654  |¬6|¬,|¬7|¬,|¬8|¬,|¬9|¬,|¬a|¬,|¬b|¬,|¬c|¬,|¬d|¬,|¬e|¬,|¬f.|;
  655  {A9}!|9|7The historical development of number 
  660  representations is a fascinating story, since 
  666  it parallels the development of civilization 
  672  itself. We would be going far a_eld is we were 
  682  to examine this history in minute detail, but 
  690  it will be instructive to look at its main features 
  700  here:|'!|9|7The earliest forms of number representations, 
  707  still found in primitive cultures, are generally 
  714  based on groups of _ngers, or piles of stones, 
  723  etc., usually with special conventions about 
  729  replacing a larger pile or group of, say, _ve 
  738  or ten objects by one object of af special kind 
  748  or in a special place. Such systems lead naturally 
  757  to the earliest ways of representing numbers 
  764  in written form, as in the systems of Babylonian, 
  773  Egyptian, Greek, Chinese, and Roman numerals, 
  779  but such notations are quite inconvenient for 
  786  performing arithmetic operations except in the 
  792  simplest cases.|'!|9|6During the twentieth century, 
  798  historians of mathematics have made extensive 
  804  studies of early cuneiform tablets found by archeologists 
  812  in the Middle East. These studies show that the 
  821  Babylonian people actually had two distinct systems 
  828  of number representation: Numbers used in everyday 
  835  business transactions were written in a notation 
  842  based on grouping by tens, hundreds, etc.; this 
  850  notation was inherited fromm earlier Mesopotamian 
  856  civilizations, and large numbers were seldom 
  862  required. When more di∃cult mathematical problems 
  868  were considered, however, Ba↓bylonian mathematicians 
  873  made extensive use of a sexagesimal (radix sixty) 
  881  positional notation which was highly developed 
  887  at least as early as 1750 {H7}B{H10}.{H7}C{H10}. 
  894  This notation was unique in that it was actually 
  903  a |ε⊃oating-point |πform of representation with 
  909  exponents omitted; the proper scale factor or 
  916  power of sixty was to be supplied by the context, 
  926  so that, for example, the numbers 2, 120, 7200, 
  935  |f1|d330|), etc. were all written in an identical 
  943  manner. The notation was especially convenient 
  949  for multiplication and division, using auxiliary 
  955  tables, since radix-point alignment had no e=ect 
  962  on the answer. As examples of this Babylonian 
  970  notation, consider the following excerpts from 
  976  early tables: The square of 30 is 15 (which may 
  986  also be read, ``The square of |f1|d32|) is |f1|d34|)''); 
  995  the reciprocal of 81|4α=↓|4(1|421)|β6|β0 is (44|426|440)|β6|
 1000  β0; and the square of the latter is (32|455|418|431|46|440)|
 1008  β6|β0. The Babylonians had a symbol for zero, 
 1016  but because of their ``⊗oating-point'' philosophy, 
 1022  it was used only within numbers, not at the right 
 1032  end to denote a scale factor. For the interesting 
 1041  story of early Babylonian mathematics, see O. 
 1048  Neugebauer, |εThe Exact Sciences in Antiquity 
 1054  |π(Princeton University Press, 1952), and B. 
 1060  L. van der Waerden, |εScience Awakening, |πtr. 
 1067  by A. Dresden (Groningen: P. Noordho=, 1954); 
 1074  see also D. E. Knuth, |εCACM |π|≡1|≡5 (1972), 
 1082  671<677.|'!|9|7Fixed-point positional notation 
 1086  was apparently developed _rst by the Maya Indians 
 1094  in central America 2000 years ago; their radix 
 1102  20 system was highly developed, especially in 
 1109  connection with astronomical records and calendar 
 1115  dates. But the Spanish conquerors destroyed nearly 
 1122  all of the Maya books on history and science, 
 1131  so we do not know how sophisticated they had 
 1140  become at arithmetic; some special-purpose multiplication 
 1146  tables have been found, but no examples of division 
 1155  are known [cf. J. Eric S. Thompson, |εContributions 
 1163  to Amer. Anthropology and History |≡7 (|πCarnegie 
 1170  Inst. of Washington, 1942), 37<62].|'!|9|7Several 
 1176  centuries before Christ, the Greek people employed 
 1183  an early form of the abacus to do their arithmetical 
 1193  calculations, using sand and/or pebbles on a 
 1200  board wwhich had rows or columns corresponding 
 1207  in a natural way to our decimal system. It is 
 1217  perhals surprising to us that the same positional 
 1225  notation was never adapted to written forms of 
 1233  numbers, since we are so accustomed to reckoning 
 1241  with the decimal system using penicl and paper; 
 1249  but the greater ease of calculating by abacus 
 1257  (since handwriting was not a common skill, and 
 1265  since abacus calculations makes it unnecessary 
 1271  to memorize addition and multiplication tables) 
 1277  probably made the Greeks feel it would be sil{U0}{H10L12M29}
folio 237 galley 2
 1285  |π58320#Computer Programming!(Knuth/Addison-Wesley)!f. 
 1287  237!ch. 4!g. 2|'{A6}!|9|6Our decimal notation, 
 1293  which di=ers from the more ancient forms primarily 
 1301  because of its _xed radix point, together with 
 1309  its symbol for zero to mark an empty position, 
 1318  was developed _rst in India among the Hindu people. 
 1327  The exact date when this notation _rst appeared 
 1335  is quite uncertain; about 600 {H7}A{H10}.{H7}D{H10}. 
 1341  seems to be a good guess. Hindu science was rather 
 1351  highly developed at that time, particularly in 
 1358  astronomy. The earliest known Hindu manuscripts 
 1364  which show this notation have numbers written 
 1371  backwards (with the most signi_cant digit at 
 1378  the right), but soon it became standard to put 
 1387  the most signi_cant digit at the left.|'!|9|7About 
 1395  750 {H7}A{H10}.{H7}D{H10}., the Hindu principles 
 1400  of decimal arithmetic were brought to Persia, 
 1407  as several important works were translated into 
 1414  Arabic; a picturesque account of this development 
 1421  is given in a Hebrew document, which has been 
 1430  translated into English in |εAMM |≡1|≡5 (1918), 
 1437  99<108. |πNot long after this, al-Khow|=7arizm|=7↓|Z 
 1443  wrote his Arabic textbook on the subject. (As 
 1451  noted in Chapter 1, our word ``algorithm'' comes 
 1459  from al-Khow|=7arizm|=7↓|Z's name.) His book 
 1464  was translated into Latin and was a strong in⊗uence 
 1473  on Leonardo Pisano (Fibonacci), whose book on 
 1480  arithmetic (1202 {H7}A{H10}.{H7}D{H10}.) played 
 1484  a major role in the spreading of Hindu-Arabic 
 1492  numerals into Europe. It is interesting to note 
 1500  that the left-to-right order of writing numbers 
 1507  was unchanged during these two transitions from 
 1514  Hindu to Arabic and from Arabic to Latin, although 
 1523  Arabic is written from right to left while Hindu 
 1532  and Latin are written from left to right. A detailed 
 1542  account on the subsequent propagation of decimal 
 1549  numeration and arithmetic into all parts of Europe 
 1557  during the period from 1200 to 1600 {H7}A{H10}.{H7}D{H10}. 
 1565  is given by David Eugene Smith in his|εHistory 
 1573  of Mathematics |≡1 |π(Boston: Ginn and Co., 1923), 
 1581  Chapers 6 and 8.|'!|9|7Decimal notation was applied 
 1589  at _rst only to integer numbers, not to fractions. 
 1598  Arabic astronomers, who required fractions in 
 1604  their star charts and other tables, continued 
 1611  to use the notation of Ptolemy (the famous Greek 
 1620  astronomer) which was based on sexagesimal fractions. 
 1627  This system still survives today, in our trigonometric 
 1635  units of ``degrees, minutes, and seconds,'' and 
 1642  also in our units of time, as a remnant of the 
 1653  original Babylonian sexagesimal notation. Early 
 1658  European mathematicians also used sexagesimal 
 1663  fractions when dealing with noninteger numbers; 
 1669  for example, Fibonacci gave the value|'{A9}1|¬P|922|¬S|97|¬P
 1675  |942|9|9ee|ε|gI|gV|94|gV|940|gV|gI|;{A9}|πas 
 1677  an approximation to the root of the equation 
 1685  |εx|g3|4α+↓|42x|g2|4α+↓|410x|4α=↓|420. |π(The 
 1687  correct answer is 1|¬0 22|¬S 7|¬C 42|9 33|ε|gI|gV 
 1695  4|gV 38|gV|gI 30|gV|gI|gI 50|gV|gI|gI|gI 15|gI|gX 
 1700  43|gX|4.|4.|4.|4.)|'|π!|9|7The use of decimal 
 1705  notation also for tenths, hundredths, etc., in 
 1712  a similar way seems to be a comparatively minor 
 1721  change; but, of course, it is hard to break with 
 1731  tradition, and sexagesimal fractions have an 
 1737  advantage over decimal fractions in that numbers 
 1744  such as |f1|d33|) can be expressed exactly in 
 1752  a simple way. Chinese mathematicians (who never 
 1759  used sexagesimals) were the _rst people to work 
 1767  with the equivalent of decimal fractions, although 
 1774  their numeral system (lacking zero) was not originally 
 1782  a positional number system in the strict sense. 
 1790  Chinese units of weights and measures were decimal, 
 1798  so that Tsu Chhung-Chih (who died c.500 {H7}A{H10}.{H7}D{H10
 1805  }. was able to express an approximation to |ε|≤p 
 1814  |πas ``3 chang, 1 chhih, 4 tshun, 1 f|=7en, 5 
 1824  li, 9 hao, 2 miao, 7 hu.'' Here chang,|4.|4.|4.|4, 
 1833  hu are units of length; 1 hu (the diameter of 
 1843  a silk thread) equals 1/10 miao, etc. The use 
 1852  of such decimal-like fractions was fairly widespread 
 1859  in China after about 1250 {H7}A{H10}.{H7}D{H10}. 
 1865  The _rst known occurrence of decimal fractions 
 1872  in a true positional system is in a 10th century 
 1882  arithmetic text written in Damascus by an obscure 
 1890  mathematician named al-Uql|=7↓|Zdis|=7↓|Z (``the 
 1894  Euclidean''). He used the symbol |¬S for a decimal 
 1903  point, and expressed some fractions and approximate 
 1910  square and cube roots; but he did not realize 
 1919  that the integer and fractions parts of numbers 
 1927  could be multiplied simultaneously. His work 
 1933  did not become well known, and _ve more centuries 
 1942  passed before decimal fractions were reinvented 
 1948  by a Persian mathematician, al-Kash|=7↓|Z, who 
 1954  died c. 1436. Al-Kash|=7↓|Z was a highly skillful 
 1962  calculator, who gave the value of 2|ε|≤p |πas 
 1970  follows, correct to 16 decimal places:|'{A9}|J#>
 1977  |∂!!!!|∂!!!!!!!!!!!!!!!!!!!!!!!!|∂|E|;|>integer|;
 1980  fractions|;>{B2}|J#>|∂!!|∂!!|∂!|9|∂!|9|∂!|9|∂!|9|∂!|9|∂!|9|∂
 1983  !|9|∂!|9|∂!|9|∂!|9|∂!|9|∂!|9|∂!|9|∂!|9|∂!|9|∂!|9|∂|E|;
 1984  |>0|;6|;2|;8|;3|;1|;8|;5|;3|;0|;7|;1|;7|;9|;5|;
 2000  8|;6|;5|;>{B2}|J#>This was by far the best approximation 
 2012  to |ε|≤p |πknown until Ludolph van Ceulen laboriously 
 2020  calculated 35 decimal places during the period 
 2027  1596<1610. The earliest known example of decimal 
 2034  fractions in Europe occurs in a 15th-century 
 2041  text where, for example, 153.5 is multiplied 
 2048  by 16.25 to get 2494.375; this was referred to 
 2057  as a ``Turkish method.'' In 1525, Christof Rudol= 
 2065  of Germany discovered decimal fractions for himself; 
 2072  his work never became well-known, either. Fran|=&cois 
 2079  Vi|=2ete suggested the idea again in 1579. Finally, 
 2087  an arithmetic text by Simon Stevin of Belgium, 
 2095  who independently hit on the idea of decimal 
 2103  fractions in 1585, became popular. His work, 
 2110  and the discovery of logarithms soon afterwards, 
 2117  made decimal fractions very common in Europe 
 2124  during the 17th century. [See D. E. Smith, |εHistory 
 2133  of Mathematics |≡2 |π(Boston: Ginn and Co., 1925), 
 2141  228<247, and C. B. Boyer, |εHistory of Mathematics 
 2149  |π(New York: Wiley, 1968), for further remarks 
 2156  and references.]|'!|9|7The binary system of notation 
 2163  has its own interesting history. Many primitive 
 2170  tribes in existence today are known to use a 
 2179  binary or ``pair'' system of counting (making 
 2186  groups of two instead of _ve or ten), but they 
 2196  do not count in a true radix 2 system, since 
 2206  they do not treat powers of 2 in a special manner. 
 2217  See |εThe Di⊃usion of Counting Practices |πby 
 2224  Abraham Seidenberg, Univ. Calif. Publ. in Math. 
 2231  |≡3 (1960), 215<300, for interesting details 
 2237  about primitive number systems. Another ``primitive'' 
 2243  example of an essentially binary system is the 
 2251  conventional musical notation for expressing 
 2256  rhythms and durations of time.|'!|9|7Nondecimal 
 2262  number systems were discussed in Europe during 
 2269  the seventeenth century. For many years astronomers 
 2276  had occasionally used sexagesimal arithmetic 
 2281  both for the integer and the fractional parts 
 2289  of numbers, primarily when performing multiplication 
 2295  [see John Wallis, |εTreatise of Algebra |π(Oxford, 
 2302  1685), 18<22, 30]. The fact that |εany |πpositive 
 2310  number could serve as radix was apparently _rst 
 2318  stated in print by Blaise Pascal in |εDe numeris 
 2327  multiplicibus, |πwhich was written about 1658 
 2333  [see Pascal's |ε|9Euvres Compl|=2etes |π(Paris: 
 2338  |=⊂Editions de Seuil, 1963), 84<89]. Pascal woote, 
 2345  ``Denaria enim ex institute hominum, non ex necessitate 
 2353  naturae ut vulgus arbitratur, et sane satis inepte, 
 2361  posita est''; i.e., ``The decimal system has 
 2368  been established, somewhat foolishly to be sure, 
 2375  according to man's custom, not from a natural 
 2383  necessity as most people would think.'' He stated 
 2391  that the duodecimal (radix twelve) system would 
 2398  be a welcome change, and he gave a rule for testing 
 2409  a duodecimal number for divisibility by 9. Erhard 
 2417  Weigel proposed the quaternary (radix four) system 
 2424  in a series of publications beginning in 1673. 
 2432  A detailed discussion of radix twelve arithmetic 
 2439  was given by Joshua Jordaine, |εDuodecimal Arithmetick 
 2446  |π(London, 1687).|'!|9|7Although decimal notation 
 2451  was almost exclusively used for arithmetic during 
 2458  that era, other systems of weights and measures 
 2466  were rarely if ever based on multiples of 10, 
 2475  and many business transactions required a good 
 2482  deal of skill in adding quantities such as pounds, 
 2491  shillings, and pence. For centuries merchants 
 2497  had therefore learned to compute sums and di=erences 
 2505  of quantities expressed in peculiar units of 
 2512  currency, weights, and measures; and this was 
 2519  actually arithmetic in a nondecimal number system. 
 2526  The common units of liquid measure in England, 
 2534  dating from the 13th century or earlier, are 
 2542  particularly noteworthy:|'{A9}|h2 chopins|4|∂α=↓|41 
 2546  demibushel!!2 demibushels|4|∂α=↓|41 bushel or 
 2550  _rkin|E|n|;| 2 gills|4|Lα=↓|41 chopin| 2 demibushels|4|Lα=↓|
 2554  41 bushel or _rkin>| 2 chopins|4|Lα=↓|41 pint| 2 
 2561  _rkins|4|Lα=↓|41 kilderkin>| 2 pints|4|Lα=↓|41 
 2565  quart| 2 kilderkins|4|Lα=↓|41 barrel>| 2 quarts|4|Lα=↓|41 
 2570  pottle| 2 barrels|4|Lα=↓|41 hogshead>| 2 pottles|4|Lα=↓|41 
 2575  gallon| 2 hogsheads|4|Lα=↓|41 pipe>| 2 gallons|4|Lα=↓|41 
 2580  peck| 2 pipes|4|Lα=↓|41 tun>| 2 pecks|4|Lα=↓|41 
 2585  demibushel>{A9}Quantities of liquid zxpressed 
 2590  in gallons, pottles, quarts, pints, etc. were 
 2597  essentially written in binary notation. Perhaps 
 2603  the true inventors of binary artihmetic were 
 2610  English wine merchants*3|'!|9|7The _rst known 
 2616  appearance of binary notation was about 1605 
 2623  in some unpublished manuscripts of Thomas Harriot 
 2630  (1560<1621). Harriot was a creative man, who 
 2637  came to America as a representative of Sir Walter 
 2646  Raleigh; he invented (among other things) a notation 
 2654  like that now used for ``less than'' and ``greater 
 2663  than'' relations; but for some reason he chose 
 2671  not to publish many of his discoveries. Excerpts 
 2679  from his notes on binary arithmetic have been 
 2687  reproduced by John W. Shirley, |εAmer. J. Physics 
 2695  |≡1|≡9 (1951), 452<454. |πThe _rst published 
 2701  discussion of the binary system was given in 
 2709  a comparatively little-known work by a Spanish 
 2716  bishop, Juan Caramuel Lobkowitz, |εMathesis biceps 
 2722  |≡1 |π(Campaniae, 1670), 45<48; Caramuel discussed 
 2728  the representation of numbers in radices 2, 3, 
 2736  4, 5, 6, 7, 8, 9, 10, 12, and 60 at some length, 
 2749  but gave no examples of arithmetic operations 
 2756  in nondecimal systems (except for the trivial 
 2763  operation of adding unity).|'|Hβ*?*?*?*?{U0}{H10L12M29}|π58320#C
folio 241 galley 3
 2767  omputer Programming!(Knuth/Addison-Wesley)!f. 
 2769  241!ch. 4!g. 3|'{A6}!|9|7Ultimately, an article 
 2775  by G. W. Leibnitz |ε[Memoires de l'Academie Royale 
 2783  des Sciences |π(Paris, 1703), 110<116], which 
 2789  illustrated binary addition, subtraction, multiplication, 
 2794  and division, really brought binary notation 
 2800  into the limelight, and this article is usually 
 2808  referred to as the birth of radix 2 arithmetic. 
 2817  Leibnitz later referred to the binary system 
 2824  quite frequently [cf. W. Ahrens, |εMathematische 
 2830  Unterhaltungen und Spiele |≡1 |π(Leipzig: Teubner, 
 2836  1910), 27<28]. He did not recommend it for practical 
 2845  calculations, but he stressed its importance 
 2851  in number-theoretical investigations, since patterns 
 2856  in number sequences are often more apparent in 
 2864  binary notation than they are in decimal; he 
 2872  also saw a mystical signi_cance in the fact that 
 2881  everything is expressible in terms of zero and 
 2889  one [see Laplace, |εTh|=1eorie Analytique des 
 2895  Probabilit|=1es, |π3rd ed. (Paris, 1820), cix].|'
 2901  !|9|7It is interesting to note that the important 
 2909  concept of negative powers to the right of the 
 2918  radix point was not yet well understood at that 
 2927  time. Leibnitz asked James Bernoulli to calculate 
 2934  |ε|≤p |πin the binary system, and Bernoulli ``solved'' 
 2942  the problem by taking a 35-digit approximation 
 2949  to |ε|≤p, |πmultiplying it by 10|g3|g5, and then 
 2957  expressing this integer in the binary system 
 2964  as his answer. On a smaller scale this would 
 2973  be like saying that |ε|≤p|4|¬V|43.14, |πand (314)|β1|β0|4α=↓
 2979  |4(100111010)|β2; hence |ε|≤p |πin binary is 
 2985  100111010*3 [See Leibnitz, |εMath. Schriften |π(ed. 
 2991  Gehrhardt), |≡3 (Halle: 1855), 97; two of the 
 2999  118 bits in the answer are incorrect, due to 
 3008  computational errors.] The motive for Bernoulli's 
 3014  calculation was apparently to see whether any 
 3021  simple pattern could be observed in this representation 
 3029  of |ε|≤p.|'|π!|9|6Charles XII of Sweden, whose 
 3036  talent for mathematics perhaps exceeded that 
 3042  of all other kings in the history of the world, 
 3052  hit on the idea of radix-8 srithmetic about 1717. 
 3061  This was probably his own invention, although 
 3068  he had met Leibnitz brie⊗y in 1707. Charles felt 
 3077  radix 8 or 64 would be more convenient for calculation 
 3087  than the decimal system, and he considered introducing 
 3095  octal arithmetic into Sweden; but he died in 
 3103  battle before carrying out such a change. [See 
 3111  |εThe Works of Voltaire |≡2|≡1 |π(Paris: E. R. 
 3119  DuMont, 1901), 49; E. Swedenborg, |εGentleman's 
 3125  Magazine |≡2|≡4 (1754), 423<424.]|'!|9|7|πOctal 
 3130  notation was proposed also in colonial America 
 3137  before 1750, by the Rev. Hugh Jones, rector of 
 3146  a parish in Maryland (cf. |εGentleman's Magazine 
 3153  |≡1|≡5 |π(1745), 377<379; H. R. Phalen, |εAMM 
 3160  |≡5|≡6 (1949), 361<465).|'|π!|9|7More than a 
 3166  century later, a prominent Swedisym-A*?|π!|9|7More 
 3171  than a century later, a prominent Swedish-American 
 3178  civil engineer named John W. Nystrom decided 
 3185  to carry Charles XII's plans a step further, 
 3193  by devising a complete system of numeration, 
 3200  weights, and measures based on hexadecimal (radix 
 3207  16) arithmetic. He wrote, ``I am not afraid, 
 3215  or do hot hesitate, to advocate a binary system 
 3224  of arithmetic and metrology. I know I have nature 
 3233  on my side; if I do not succeed to impress upon 
 3244  you its utility and great importance to mankind, 
 3252  it will re⊗ect that much less credit upon our 
 3261  generation, upon our scienti_c men and philosophers.'' 
 3268  Nystrom devised special means for pronouncing 
 3274  hexadecimal numbers; e.g. |≤#|¬b|¬0|¬1|¬6|¬0|≤&|β1|β6 
 3278  was to be read ``vybong, bysanton.'' His entire 
 3286  system was called the Tonal System, and it is 
 3295  described in |εJ. Franklin Inst. |≡4|≡6 (1863), 
 3302  263<275, 337<348, 402<407. |πA similar system, 
 3308  but using radix 8, was worked out by Alfred B. 
 3318  Taylor |ε[Proc. Amer. Pharmaceutical Assoc. |≡8 
 3324  (1859), 115<216; Proc. Amer. Philosophical Soc. 
 3330  |≡2|≡4 (1887), 296<366]. |πIncreased use of the 
 3337  French (metric) system of weights and measures 
 3344  prompted extensive debate about the merits of 
 3351  decimal arithmetic during that era; indeed, octal 
 3358  arithmetic was even being proposed in France 
 3365  [Aim|=1e Mariage, |εNum|=1eration par huit |π(Pars: 
 3371  Le Nonnant, 1857)].|'!|9|7The binary system was 
 3378  well-known as a curiosity ever since Leibnitz's 
 3385  time, and ab out 20 early references to it have 
 3395  been compiled by R. C. Archibald [|εAMM |≡2|≡5 
 3403  (1918), 139<142]. |πIt was applied chie⊗y to 
 3410  the calculation of powers, as explained in Section 
 3418  4.6.3, and to the analysis of certain games and 
 3427  puzzles. G. Peano |ε[Atti della R. Accademia 
 3434  delle Scienze di Torino |≡3|≡4 (1898), 47<55] 
 3441  |πused binary notation as the basis of a ``logical'' 
 3450  character set of 256 symbols. Joseph Bowden |ε[Special 
 3458  Topics in Theoretical Arithmetic |π(Garden City: 
 3464  1936), 49] gave his own system of nomenclature 
 3472  for hexadecimal numbers.|'!|9|7The book |εHistory 
 3478  of Binary and Other Nondecimal Numeration |πby 
 3485  Anton Glaser (privately printed, 1971) contains 
 3491  an informative and nearly complete discussion 
 3497  of the development of binary notation, including 
 3504  English translations of amny of the works cited 
 3512  above.|'!|9|7Increased interest in mechanical 
 3517  devices for doing arithmetic, especially for 
 3523  multiplication, led several people to consider 
 3529  the binary system for this purpose. A particularly 
 3537  delightful account of this activity appears in 
 3544  the article ``Binary Calculation'' by E. William 
 3551  Phillips |ε[Journal of the Institute of Actuaries 
 3558  |≡6|≡7 (1936), 187<221] |πtogether with a record 
 3565  of the discussion which followed a lecture he 
 3573  gave on the subject. Phillips began by saying, 
 3581  ``The ultimate aim [of this paper] is to persuade 
 3590  the whole civilized world to abandon decimal 
 3597  numeration and to use octonal [ilel, radix 8] 
 3605  numeration in its place.''|'!|9|7Modern readers 
 3611  of Phillips's article will perhaps be surprised 
 3618  to discover that a radix-8 number system was 
 3626  properly referred to as ``octonary'' or ``octonal,'' 
 3633  according to all dictionaries of the English 
 3640  language at that time, just as the radix-10 number 
 3649  system is properly called either ``denary'' or 
 3656  ``decimal''; the word ``octal'' did not appear 
 3663  in English language dictionaries until 1961, 
 3669  and it apparently originated as a term for the 
 3678  ``base'' of a certain class of vacuum tubes. 
 3686  The wordd ``hexadecimal,'' which has crept into 
 3693  our languate even more recently, is a mixture 
 3701  of Greek and Latin stems; more proper terms would 
 3710  be ``senidenary'' or ``sedecimal'' or even ``sexacecimal,'' 
 3717  but the latter is perhaps too risqu|=1e for computer 
 3726  programmers.|'!|9|7The comment by Mr. Wales which 
 3733  is quited at the beginning of this chapter has 
 3742  been taken from the discussion printed with Mr. 
 3750  Phillips's paper. Another man who attended the 
 3757  same lecture objected to the octal system for 
 3765  business purposes: ``5% becomes 3.1463 per 64, 
 3772  which sounds rather horrible.''|'!|9|7Phillips 
 3777  got the inspiration for his proposals from an 
 3785  electronic circuit which was capable of counting 
 3792  in binary [C. E. Wyn-Williams, Proc. Roy. Soc. 
 3800  London |≡A|≡1|≡3|≡6 (1932), 312<324]. Electromechanical 
 3805  and electronic circuitry for general arithmetic 
 3811  operations was developed during the late 1930's, 
 3818  notably by John V. Atanaso= and George R. Stibitz 
 3827  in the U.S.A., L. Cou∃gnal and R. Valtat in France, 
 3837  Helmut Schreyer and Konrad Zuse in Germany. All 
 3845  of these inventors used the binary system, although 
 3853  Stibitz later developed excess-3 binary-coded-decimal 
 3858  notation. A fascinating account of these early 
 3865  developments, including reprints and translations 
 3870  of important acontemporary documents, appears 
 3875  in Brian Randell's book |εThe Origins of Digital 
 3883  Computers |π(Berlin: Springer, 1973).|'!|9|7The 
 3888  _rst American high-speed computers, built in 
 3894  the early 1940's, used decimal arithmetic. But 
 3901  in 1946, an important memorandum by A. W. Burks, 
 3910  H. H. Goldstine, and J. von Neumann, in connection 
 3919  with the design of the _rst stored-program computers, 
 3927  gave detailed reasons for the deacision to make 
 3935  a radical departure from tradition and to use 
 3943  base-two notation [see John von Neumann, |εCollected 
 3950  Works |≡5|≡, 41<65]. |πSince then binary computers 
 3957  have beacome commonplace. After a dozen years 
 3964  of experience with binary machines, a discussion 
 3971  of the relative advantages and disadvantages 
 3977  of binary notation was given by W. Buchholz in 
 3986  his paper ``Fingers or Fists?'' |ε[CACM |≡2 |π(December, 
 3994  1959), 3<11].|'!|9|7The |¬m|¬i|¬x computer used 
 4000  in this book has been de_ned so that it can be 
 4011  either binary or decimal. It is interesting to 
 4019  note that nearly all |¬m|¬i|¬x programs can be 
 4027  expressed without knowing whether binary or decimal 
 4034  notation is being used#even when we are doing 
 4042  calculations involving multiple-precision arithmetic. 
 4046  Thus we _nd that the choice of radix does not 
 4056  signi_cantly in⊗uence computer programming. (Noteworthy 
 4061  exceptions to this statement, however, are the 
 4068  ``Boolean'' algorithms discussed in Section 7.1; 
 4074  see also Algorithm 4.5.2B.)|'!|9|7There are several 
 4081  di=erent methods for representing |εnegative 
 4086  |πnumbers in a computer, and this sometimes in⊗uences 
 4094  the way arithmetic is done. In order to understand 
 4103  these other notations, let us _rst consider |¬m|¬i|¬x 
 4111  as if it were a decimal computer; then each word 
 4121  contains 10 digits and a sign, e.e.,|'{A8}|→α_↓12345|467890.
 4128  |J!(2)|;{A9}This is called the |εsigned-magnitude 
 4134  |πrepresentation. Such a representation corresponds 
 4139  to common notational conventilns, so it is preferred 
 4147  by many programmers. A otential disadvantage 
 4153  is that minus zero and plus zero can both be 
 4163  represented, while they usually should mean the 
 4170  same number; this possibility requires some care 
 4177  in practive.|'!|9|7Most mechanical calculators 
 4182  that do decimal arithmetic use another system 
 4189  called |εten's complement |πnotation. If we subtract 
 4196  1 from 00000|400000, we get 99999|499999 in this 
 4204  notation; in other wods, no explicit sign is 
 4212  attached to the number, and calculation is |εdone 
 4220  modulo 10|g1|g0. |πThe number |→α_↓12345|467890 
 4225  would appear as|'{A8}87654|432110|J!(3)|;{A9}in 
 4230  ten's complement notation. It is conventional 
 4236  to regard any number whose leading digit is 5, 
 4245  6, 7, 8, or 9 as a negative value in this notation, 
 4257  although with respect to addition and subtraction 
 4264  there is no harm in regarding (3) as the number 
 4274  |→α+↓87654|432110 if it is conveneint to do so. 
 4282  There is no problem of ``minus zero'' with ten's 
 4291  complement notation. The major di=erence between 
 4297  signed magnitude and ten's complement notation. 
 4303  The major di=erence between signed magnitude 
 4309  and ten's complement notations in practice is 
 4316  that shigting right does not divide the magnitude 
 4324  by ten; for example, the number |→α_↓11|4α=↓|4.|4.|4.|4.|499
 4330  989, shifted right one, gives .|4.|4.|499998|4α=↓|4|→α_↓2 
 4336  |π(assuming that a shift to the right inserts 
 4344  ``9'' as the leading digit when the number shifted 
 4353  is negative). In general, |εx |πshifted right 
 4360  one digit in ten's complement notation will give 
 4368  |"l|εx/10|"L, |πwhether |εx |πis positive or 
 4374  negative. A possible disadvantage of the ten's 
 4381  complement system is the fact that it is not 
 4390  symmetric about zero; the largest negative number 
 4397  representable in |ε{U0}{H10L12M29}|π58320#Computer 
folio 245 galley 4
 4400  Programming!(Knuth/Addison-Wesley)!f. 245!ch. 
 4402  4!g. 4|'{A6}!|9|7Another notation which has been 
 4409  used since the earliest days of high-speed computers 
 4417  is called |εnines' complement |πrepresentation. 
 4422  In this case the number |→α_↓12345|467890 would 
 4429  appear as|'{A9}87654||432109.|J!(4)|;{A9}Each 
 4433  digit of a negative number |ε|→α_↓x |πis equal 
 4441  to 9 minus the corresponding digit of |εx. |πIt 
 4450  is not di∃cult to see that the nines' complement 
 4459  notation for a negative number is always one 
 4467  less than the corresponding ten's complement 
 4473  notation; addition and subtraction are done modulo 
 4480  10|g1|g0|4α_↓|41, which means that a carry o= 
 4487  the left end is to be added at the right end. 
 4498  (Cf. Section 3.2.1.1) Again there is a potential 
 4506  problem with minus zero, since 99999|499999 and 
 4513  00000|400000 denote the same value.|'!|9|7The 
 4519  ideas just explained for base-10 arithmetic apply 
 4526  in a similar way to base-2 arithmetic, where 
 4534  we have |εsigned magnitude, two's complement, 
 4540  |πand |εones' complement |πnotations. The |¬m|¬i|¬x 
 4546  computer, as used in the examples of this chapter, 
 4555  deals only with signed-magnitude arithmetic: 
 4560  alternative procedures for complement notations 
 4565  are discussed in the accompanying text when it 
 4573  is important to do so.|'!|9|7Most computer manuals 
 4581  tell us that the machine's circuitry assumes 
 4588  that the radix point is situated in a particular 
 4597  place within each computer word. This advice 
 4604  should usually be disregarded; it is better to 
 4612  learn the rules concerning where the radix point 
 4620  will appear in the result of an instruction if 
 4629  we assume that it lies in a certain place beforehand. 
 4639  For example, in the case of |¬m|¬i|¬x we could 
 4648  regard our operands either as integers with the 
 4656  radix point at the extreme right, or as fractions 
 4665  with the radix point at the extreme left, or 
 4674  as some mixture of these two extremes; the rules 
 4683  for the appearance of the radix point in each 
 4692  result are straightforward.|'!|9|7It is easy 
 4698  to see that there is a simple relation between 
 4707  radix |εb |πand radix |εb|gk:|'{A9}(.|4.|4.|4a|β3a|β2a|β1a|β
 4712  0.a|βα_↓|β1a|βα_↓|β2|4.|4.|4.)|βb|4α=↓|4(.|4.|4.|4A|β3A|β2A|
 4712  β1A|β0.A|βα_↓|β1A|βα_↓|β2|4.|4.|4.)|βb|lk,|J!(5)|;
 4713  |πwhere|'|εA|βj|4α=↓|4(a|βk|βj|βα+↓|βk|βα_↓|β1|4.|4.|4.|4a|β
 4714  k|βj|βα+↓|β1a|βk|βj)|βb;|;{A9}|πsee exercise 
 4717  8. Thus we obtain the simple techniques for converting 
 4726  at sight between, say, binary and octal notation.|'
 4734  !|9|7There are many interesting variations on 
 4740  positional number systems besides the standard 
 4746  |εb-|πary systems discussed so far. For example, 
 4753  we might have numbers in base (|→α_↓10), so that|'
 4762  {A9}|ε(.|4.|4.|4a|β3a|β2a|β1a|β0.a|βα_↓|β1a|βα_↓|β2|4.|4.|4.
 4762  )|βα_↓|β1|β0|'{A12}|∂α=↓|4|¬O|4|¬O|4|¬O|4α_↓|4100a|β3|4α+↓|4
 4763  100a|β2|4α_↓|410a|β1|4α+↓|4a|β0|4α_↓|4|f1|d310|)a|βα_↓|β1|4α
 4763  +↓|4|f1|d3100|)a|βα_↓|β2|4α_↓|4|¬O|4|¬O|4|¬O|4.|E|?
 4764  {B12}|Lα=↓|4|¬O|4|¬O|4|¬O|4α+↓|4a|β3(|→α_↓10)|g3|4α+↓|4a|β2(
 4764  |→α_↓10)|g2|4α+↓|4a|β1(|→α_↓10)|g1|4α+↓|4a|β0|4α+↓|4|¬O|4|¬O
 4764  |4|¬O>{A12}{A9}|πHere the individual digits satisfy 
 4770  0|4|¬E|4|εa|βk|4|¬E|49 |πjust as in the decimal 
 4776  system. The number 12345|467890 would appear 
 4782  in the ``negadecimal'' system as|'{A9}(1|493755|473910)|βα_↓
 4787  |β1|β0,|J!(6)|;{A9}since the latter represents 
 4792  10305070900|4α_↓|49070503010. It is interesting 
 4796  to note that the negative of this number, |→α_↓12345|467890,
 4804   would be written|'{A9}(28466|448290)|βα_↓|β1|β0,|J!(7)|;
 4809  {A9}and, in fact, |εevery real number whether 
 4816  positive or negative can be represented without 
 4823  a sign |πin the |→α_↓10 system.|'!|9|7Negative-base 
 4830  systems were _rst considered by Vittorio Gr|=4unwald 
 4837  |ε[Giornale di matematiche di Battaglini |≡2|≡3 
 4843  (1885), 203<221, 367], |πwho explained how to 
 4850  perform the four arithmetic operations in such 
 4857  systems; he also discussed root extraction, divisibility 
 4864  tests, and rdadix conversion. However, since 
 4870  his work was published in such an obscure journal, 
 4879  it seems to have had no e=ect on other research, 
 4889  and it was soon forgotten. The next mention of 
 4898  negative-base systems in literature was apparently 
 4904  by A. J. Kempner |ε[AMM |≡4|≡3 (1936), 610<617], 
 4912  |πwho discussed the properties of non-integer 
 4918  radices and remarked in a footnote that negative 
 4926  radices would be feasible too. After twenry more 
 4934  years the idea was rediscovered again, this time 
 4942  by Z. Pawlak and A. Wakulicz |ε[Bulletin de l'Academie 
 4951  Polonaise des Sciences, |πClasse III, |≡5 (1957), 
 4958  233<236; S|=1erie des sciences techniques |≡7 
 4964  (1959), 713<721], and by L. Wadel [|εIRE Transactions 
 4972  |π|≡E|≡C|≡-|≡6 (1957), 123]. For further references 
 4978  see IEEE |εTransactions |π|≡E|≡C|≡-|≡1|≡2 (1963), 
 4983  274<276; |εComputer Design |≡6 |π(May, 1967), 
 4989  52<63. (There is evidence that the idea of negative 
 4998  bases occurred independently to quite a few people. 
 5006  For example, D. E. Knuth had discussed negative-base 
 5014  systems in 1955 in a short paper submitted to 
 5023  a ``science talent search'' contest for high-school 
 5030  seniore, together with a further generalization 
 5036  to complex-valued bases.)|'!|9|7The base 2|εi 
 5042  |πgives an interesting system called the ``quater-imaginary'
 5048  ' number system (by analogy with ``quaternary'') 
 5055  since |εevery complex number canf be represented 
 5062  with the digits |*/0, 1, 2, |\and |*/3|\ without 
 5071  a sign |πin this system. [See |εCACM |≡3 (1960), 
 5080  245<247.] |πFor example,|'{A9}|ε(11210.31)|β2|βi|4|∂α=↓|41|4
 5083  |¬O|416|4α+↓|41|4|¬O|4(|→α_↓8i)|4α+↓|42|4|¬O|4(|→α_↓4)|4α+↓|
 5083  41|4|¬O|4(2i)|4α+↓|43|4|¬O|4(|→α_↓|f1|d32|)i)|4α+↓|41(|→α_↓|
 5083  f1|d34|))|;{A4}|Lα=↓|47|f3|d34|)|4α_↓|47|f1|d32|)i.>
 5085  {A9}|πHere the number |ε(a|β2|βn|4.|4.|4.|4a|β1a|β0.a|βα_↓|β
 5088  1|4.|4.|4.|4a|βα_↓|β2|βk)2|βi |πis equal to|'
 5092  {A9}|ε(a|β2|βn|4.|4.|4.|4a|β2a|β0.a|βα_↓|β2|4.|4.|4.|4a|βα_↓
 5092  |β2|βk)|βα_↓|β4|4α+↓|42i(a|β2|βn|βα_↓|β1|4.|4.|4.|4a|β3a|β1.
 5092  a|βα_↓|β1|4.|4.|4.|4a|βα_↓|β2|βk|βα+↓|β1)|βα_↓|β4,|;
 5093  {A9}|πso conversion to and from quater-imaginary 
 5099  notation reduces to conversion to and from negative 
 5107  quaternary representation of the real and imaginary 
 5114  parts. The interesting property of this system 
 5121  is that it allows multiplication and division 
 5128  of complex numbers to be done in a fairly uni_ed 
 5138  manner without treating real and imaginary parts 
 5145  separately. For example, we can multiply two 
 5152  numbers in this system much as we do with any 
 5162  base, merely using a di=erent ``carry'' rule: 
 5169  whenever a digit exceeds 4 we subtract 4 and 
 5178  ``carry'' a |→α_↓1 two columns to the left; when 
 5187  a digit is negative, we add four to it and ``carry'' 
 5198  |→α+↓1 two columns to the left. A study of the 
 5208  following example shows this peculiar carry rule 
 5215  at work:|'{A9}|h|∂0|42|41|42|42|42|42|42|42!!|∂[|→α_↓19|4α_↓
 5217  |4180i]|E|n|;|L!!!|21|42|42|43|41|L[9|4α_↓|4|ε10i]>
 5219  |L!!!|21|42|42|43|41|L[9|4α_↓|410i]>{B2}|L!!!|2####>
 5221  |L!!!|21|42|42|43|41>|L1|40|43|42|40|42|41|43>
 5223  |L!|9|11|43|40|42|42>|L|9|51|43|40|42|42>|L1|42|42|43|41>
 5226  {B2}|L#######>|L0|42|41|43|43|43|41|42|41|L[|→α_↓19|4α_↓|418
 5227  0i]>{A9}|π!|9|7A similar system which uses just 
 5234  the digits 0 and 1 may be based on {H11}|¬H{H10}|v42|)|εi, 
 5244  |πbut this requires an in_nite nonrepeating expansion 
 5251  for the simple number ``|εi'' |πitself.|'!|9|7A 
 5258  ``binary'' complex number system may also be 
 5265  obtained by using the base |εi|4α_↓|41, |πas 
 5272  suggested by W. Penney [|εJACM |≡1|≡2 (1965), 
 5279  247<248]:|'{A9}(.|4.|4.|4a|β4a|β3a|β2a|β1a|β0.a|βα_↓|β1|4.|4
 5280  .|4.)|βi|βα_↓|β1|'α=↓|4|¬O|4|¬O|4|¬O|4|→α_↓4a|β4|4α+↓|4(2|4α
 5281  +↓|42i)a|β3|4α_↓|42ia|β2|4α+↓|4(i|4α_↓|41)a|β1|4α+↓|4a|β0|4α
 5281  _↓|4|f1|d32|)(i|4α+↓|41)a|βα_↓|β1|4α+↓|4|¬O|4|¬O|4|¬O|4.|?
 5282  {A9}|π!|9|7In this system, only the digits 0 
 5289  and 1 are needed. One way to whow that every 
 5299  complex number has such a representation is to 
 5307  consider the interesting set |εS |πshown in Fig. 
 5315  1; this set is, by de_nition, all points which 
 5324  can be written as |ε|¬K|ur|)k|¬R1|)|4a|βk(i|4α_↓|41)|gα_↓|gk
 5328  , |πfor an in_nite sequence |εa|β1, a|β2, a|β3, 
 5336  . . . |πof zeros and ones. Figure 1 shows how 
 5347  |εS |πcan be decomposed into 256 pieces congruent 
 5355  to |f1|d316|)|εS; |πnote that if the diagram 
 5362  of |εS |πis rotated counterclockwise by 135|¬P, 
 5369  we obtain two adjacent sets congruent to (1/{H11}|¬H{H10}|v4
 5376  2|))|εS |π(since |ε(i|4α_↓|41)S|4α=↓|4S|4|↔q|4(S|4α+↓|41){H1
 5378  2}){H10}. |πFor details of a proof that |εS |πcontains 
 5387  all complex numbers that are of su∃ciently small 
 5395  magnitude, see exercise 18. (Actually, the boundary 
 5402  of |εS |πcontains many jagged edges; these corners 
 5410  have been rounded o= in Figure 1.)|'|Hβ*?*?*?{U0}{H10L12M29}|π5
folio 249 galley 5
 5417  8320#Computer Programming!(Knuth/Addison-Wesley)!f. 
 5419  249!ch. 4!g. 5|'{A6}{H9L11}|≡F|≡i|≡g|≡. |≡1|≡.|9|4The 
 5424  set |εS. |π(Illustration by P. M. Farmwald, R. 
 5432  W. Gosper, and R. E. Mass.)|;{A7}{H10L12}!|9|7Perhaps 
 5439  the prettiest number system of all is the |εbalanced 
 5448  ternary |πnotation, which consists of base 3 
 5455  representation using the ``trits'' |→α_↓1, 0, 
 5461  |→α+↓1 instead of 0, 1, and 2. If we use the 
 5472  symbol |=∩1 to stand for |→α_↓1, we have the 
 5481  following examples of balanced ternary numbers:|'
 5487  {A9}|∂!!!!!!!!|6|∂!!!|∂!!!|9|2|∂|E|;|>Balanced 
 5490  ternary|;|;Decimal|;>{A3}|>|9|51|40|4|=∩1|'|;
 5497  |9|2!|4|48|'>|>1|41|4|=∩1|40.|=∩1|4|=∩1|'|;|9|2|9|732|f5|d39
 5502  |)|;>|>|=∩1|4|=∩1|41|40.1|41|'|;|9|2|→α_↓32|f5|d39|)|'
 5508  >|>|=∩1|4|=∩1|41|40|'|;|9|2|→α_↓33|'>|>!!|60.1|41|41|41|41|4
 5515  .|4.|4.|'|;|9|2|9|7!|2|f1|d32|)|'>{A9}!|9|7The 
 5520  balanced ternary number system has many pleasat 
 5527  properties:|'{A4}{I2.9H}!|9|7a)|9|1The negative 
 5530  of a number is obtained by interchanging 1 and 
 5539  |=∩1.|'!|9|7b)|9The sign of a number is given 
 5547  by its most signi_cant nonzero ``trit,'' and 
 5554  more generally we can compare any two numbers 
 5562  by reading them from left to right and using 
 5571  lexicographic order, as in the decimal system.|'
 5578  !|9|7c)|9|2The operation of rounding to the nearest 
 5585  integer is identical to truncation (i.e., deleting 
 5592  everything to the right of the decimal point).|'
 5600  {A6}{IC}Addition in the balanced ternary system 
 5606  is quite simple, using the table|'{A9}|9|1|=∩1|9|9|1|=∩1|9|=
 5612  ∩1|9|2|9|1|=∩1|9|=∩1|9|2|=∩1|9|2|=∩1|9|2|=∩1|9|2|=∩1|9|2|9|1
 5612  0|9|10|9|20|9|20|9|20|9|20|9|20|9|20|9|2|9|10|9|11|9|21|9|21
 5612  |9|21|9|21|9|21|9|11|9|2|9|11|9|1|9|11|'|9|1|=∩1|9|9|1|=∩1|9
 5613  |=∩1|9|9|30|90|9|20|9|21|9|21|9|21!|3|=∩1|9|1|=∩1|9|2|=∩1|9|
 5613  20|9|20|9|20|9|21|9|21!|31|9|1|=∩1|9|2|=∩1|9|2|=∩1|9|20|9|20
 5613  |9|2|9|10|9|11|9|2|9|11!|21|'|9|1|=∩1!|10|91!|3|=∩1|90|9|21|
 5614  9|2|=∩1|9|20|9|21!|3|=∩1|9|10|9|21|9|2|=∩1|9|20|9|21|9|2|=∩1
 5614  |9|20!|31|9|1|=∩1|9|20|9|21|9|2|=∩1|9|20!|31|9|1|=∩1!|30!|21
 5614  |'{B2}|J#>|=∩10|9|=∩11|9|=∩1|9|2|=∩11|9|=∩1|9|20|9|2|=∩1|9|2
 5616  0|9|21|9|2|=∩11|9|1|=∩1|9|20|9|2|=∩1|9|20|9|21|9|20|9|21|9|2
 5616  1|=∩1|9|1|=∩1|9|20|9|21|9|20|9|21|9|21|=∩1|9|11|9|21|=∩1|9|1
 5616  10|'{A9}(The three inputs to the addition are 
 5624  the digits of the numbers to be added and the 
 5634  carry digits.) Subtraction is negation followed 
 5640  by addition; and multiplicationalso reduces to 
 5646  negation and addition, as in the following example:|'
 5654  {A9}|∂!!|61|4|=∩1|40|4|=∩1!!|∂[17]|;|L!!|61|4|=∩1|40|4|=∩1|L
 5655  [17]>{B2}|L!!|6###>|L!!|6|=∩1|41|40|41>|L|9|5|=∩1|41|40|41|4
 5658  0>|L1|4|=∩1|40|4|=∩1>{B2}|L#####>|L0|41|41|4|=∩1|4|=∩1|40|41
 5661  |L[289]>{A9}For division, see exercise 4.3.1<31.|'
 5667  !|9|7One way to _nd the representation of a number 
 5676  in the balanced ternary system is to start by 
 5685  representing it in the ternary notation; for 
 5692  example,|'{A9}208.3|4α=↓|4(21201.022002200220|4.|4.|4.)|β3.|
 5693  ;{A9}(A very simple pencil-and-paper method for 
 5700  converting to ternary notation is given in exercise 
 5708  4.4<12.) Now add the in_nite number .|4.|4.|411111.11111|4.|
 5714  4.|4. in ternary notation; we obtain, in the 
 5722  above example,|'{A9}(.|4.|4.|411111210012.210121012101|4.|4.
 5724  |4.)|β3.|;{A9}Finally, subtract .|4.|4.|411111.11111|4.|4.|4
 5727  . by decrementing each digit; we get|'{A6}208.3|4α=↓|4(10|v4
 5734  11|)01.10|=∩1010|=∩1010|=∩10|4.|4.|4.)|β3.|J!(8)|;
 5735  {A9}This process may clearly be made rigorous 
 5742  if we replace the arti_cial in_nite number .|4.|4.|411111.11
 5749  111|4.|4.|4. by a number with suitably many ones.|'
 5757  !|9|7Representation of numbers in the balanced 
 5763  ternary system is implicitly present in a famous 
 5771  mathematical puzzle, which is commonly called 
 5777  ``Bachet's problem of weights,'' although it 
 5783  was already stated by Fibonacci four centuries 
 5790  before Bachet wrote his book. [See W. Ahrens, 
 5798  |εMathematische Unterhaltungen und Spiele |≡1 
 5803  |π(Leipzig: Teubner, 1910), Sir John Leslie [|εThe 
 5810  Philosophy of Arithmetic |π(Edinburgh, 1817); 
 5815  see pp. 33<34, J. Colson |ε[Philos. Trans. |≡3|≡4 
 5823  (1726), 161<173], |πand independently by Sir 
 5829  John Leslie |ε[The Philosophy of Arithmetic |π(Edinburgh, 
 5836  1817); see pp. 33<34, 54, 64<65, 117, 150], and 
 5845  independently by A. Cauchy |ε[Comptes Rendus 
 5851  |≡1|≡1 |π(Paris, 1840), 789<798], who pointed 
 5857  out that negative digits make it unnecessary 
 5864  for a person to memorize the multiplication table 
 5872  past 5|4α⊗↓|45. The _rst true appearance of ``pure'' 
 5880  balanced ternary notation was in an article by 
 5888  L|=1eon Lalanne |ε[Comptes Rendus |≡1|≡1 |π(Paris, 
 5894  1840), 903<905], who was a designer of mechanical 
 5902  devices for arithmetic. The system was mentioned 
 5909  only rarely for 100 years after Lalanne's paper, 
 5917  until the development of the _rst electronic 
 5924  computers at the Moore School of Electrical Engineering 
 5932  in 1945<1946; at that time it was given serious 
 5941  consideration along with the binary system as 
 5948  a possible replacement for the decimal system. 
 5955  The complexity of arithmetic circuitry for balanced 
 5962  ternary arithmetic is not much greater than it 
 5970  is for the binary system, and a given number 
 5979  requires only ln|42/ln|43|4|¬V|463% as many digit 
 5985  positions for its representation. Discussionf 
 5990  of the balanced ternary number system appear 
 5997  in |εAMM |≡5|≡7 (1950), 90<93; |πand in |εHigh-speed 
 6005  Computing Devices, |πEngineering Research Associates 
 6010  (McGraw-Hill, 1950), 287<289. The experimental 
 6015  Russian computer |¬s|¬e|¬t|¬u|¬n was based on 
 6021  balanced ternary notation [see |εCACM |≡3 (1960), 
 6028  149<150], |πand perhaps the symmetric properties 
 6034  and simple arithmetic of this number system will 
 6042  prove to be quite important some day (when the 
 6051  ``⊗ip-⊗op'' is replaced by a ``⊗ip-⊗ap-⊗op'').|'
 6057  !|9|7Another important generalization of the 
 6062  simple positional notation is a |εmixed radix 
 6069  |πsystem. If we have a sequence of numbers |↔b|εb|βk|↔v 
 6078  |π(where |εk |πmay be negative), we de_ne|'{A9}|ε|↔d|(.|4.|4
 6085  .|4,|4a|β3,|5a|β2,|5a|β1,|5a|β0;|9|1a|βα_↓|β1.|5a|βα_↓|β2,|5
 6085  .|4.|4.|d5.|4.|4.|4,|4b|β3,|4b|β2,|4b|β1,|4b|β0;|9b|βα_↓|β1,
 6085  |4b|βα_↓|β2,|4.|4.|4.|)|↔f|;{A4}α=↓|4|¬O|4|¬O|4|¬O|4α+↓|4a|β
 6086  3b|β2b|β1b|β0|4αt↓|4a|β2b|β1b|β0|4α+↓|4a|β1b|β0|4α+↓|4a|β0|4
 6086  α+↓|4a|βα_↓|β1/b|βα_↓|β1|4α+↓|4a|βα_↓|β2/b|βα_↓|β1b|βα_↓|β2|
 6086  4α+↓|4|¬O|4|¬O|4|¬O|4.|;(9)|?{A9}|πIn the simplest 
 6091  mixed-radix systems, we work only with integers; 
 6098  we let |εb|β0, b|β1, b|β2,|4.|4.|4. |πbe integers 
 6105  greater than one, and deal only with numbers 
 6113  that have no radix point, where |εa|βk |πis required 
 6122  to lie in the range 0|4|¬E|4|εa|βk|4|¬W|4b|βk.|'
 6128  |π!|9|7One of the most important mixed radix 
 6135  systems is the |εfactorial number system, |πwhere 
 6142  |εb|βk|4α=↓|4k|4α+↓|42. |πUsing this system, 
 6146  we can represent every positive integer uniquely 
 6153  in the form|'{A9}|εc|βnn*3|4α+↓|4c|βn|βα_↓|β1(n|4α_↓|41)*3|4α+
 6156  ↓|4|¬O|4|¬O|4|¬O|4α+↓|4c|β22*3|4α+↓|4c|β1|J!(10)|;
 6157  {A9}|πwhere |ε0|4|¬E|4c|βk|4|¬E|4k, |πand |εc|βn|4|=|↔6α=↓|4
 6160  0. |π(See Algorithm 3.32P.)|'!|9|7Mixed-radix 
 6165  systems are familiar in everyday life, when we 
 6173  deal with units of measure. For example, the 
 6181  quantity ``3 weeks, 2 days, 9 hours, 22 minutes, 
 6190  57 seconds, and 492 milliseconds'' is equal to|'
 6198  {A9}|↔d|(3,|42,|4|9|19,|422,|457;|9|9|1492|d5|9|1|97,|424,|4
 6198  60,|460;|91000|)|↔f|4seconds.|;{A9}The quantity 
 6201  ``10 pounds, 6 shillings, and trhuppence ha'penny'' 
 6208  was once [|f10,|d55|)|4|f|9|16,|d520,|)|4|f|9|13;|d512;|)|4|
 6210  f1|d52|)] pence in English currency, before England 
 6217  changed to a pure decimal monettary system.|'
 6224  !|9|7It is possible to add and subtract mixed 
 6232  radix numbers by using a straightforward generalization 
 6239  of the usual addition and subtraction algorithms, 
 6246  provided of course that the same mixed radix 
 6254  system is being used for both operands (see exercise 
 6263  4.3.1<9). Similarly, we can easily multiply or 
 6270  divide a mixed-radix number by small integer 
 6277  constants, using simple extensions of the familiar 
 6284  pencil-and-paper methods.|'!|9|7Mixed-radix systems 
 6288  were _rst discussed generally by Georg Cantor 
 6295  |ε[Zeitschrift f|=4ur Mathematik und Physik |≡1|≡4 
 6301  (1869), 121<128]. |πFor further information about 
 6307  mixed-radix system, see exercises 26 and 29.|'
 6314  !|9|7Besides the systems described in this section, 
 6321  there are several other ways to represent numbers, 
 6329  which are mentioned elsewhere in this series: 
 6336  the binomial number system (exercise 1.2.6<56); 
 6342  the Fibonacci number system (exercise 1.2.8<34); 
 6348  the phi number system (exercise 1.2.8<35); modular 
 6355  representations (Section 4.3.2); Gray code (Section 
 6361  7.2.1); and roman numerals (Section 9.1).|'!|9|7Some 
 6368  questions concerning |εirrational |πradices have 
 6373  been investigated by W. Parry, |εActa Mathematica, 
 6380  |πAcad. Sci. Hung., |≡1|≡1 (1960), 401<416.|'
 6386  {A24}|∨E|∨X|∨E|∨R|∨C|∨I|∨S|∨E|∨S|'{A11}{H9L11}|9|1|≡1|≡.|9|4
 6387  [|*/|↔O|↔C|\] Express the numbers |→α_↓10, |→α_↓9,|4.|4.|4.|4
 6392  , 9, 10 in the base |→α_↓2 number system.|'{A3}|9|1|≡2|≡.|9|
 6401  4[|*/|↔P|↔M|\] Consider the following four number 
 6407  systems: (a) binary (signed magnitude); (b) negative 
 6414  binary (radix |→α_↓2); (c) balanced ternary; 
 6420  and (d) radix |εb|4α=↓|4|f1|d310|). |πUse each 
 6426  of these number systems to express each of the 
 6435  following three numbers: (i) |→α_↓49; (ii) |→α_↓3|f1|d37|) 
 6442  (show the repeating cycle); (iii) |ε|≤p |π(to 
 6449  a few signi_cant _gures).|'{A3}|9|1|≡3|≡.|9|4[|*/|↔P|↔c|\] 
 6454  Express |→α_↓49|4α+↓|4|εi |πin the quater-imaginary 
 6459  system.|'{A3}|9|1|≡4|≡.|9|4[|*/|↔O|↔C|\] Assume 
 6462  that we have a |¬m|¬i|¬x program in which location 
 6471  |¬a contains a number for which the radix point 
 6480  lies between bytes 3 and 4, while location |¬b 
 6489  contains a number whose radix point lies between 
 6497  bytes 2 and 3. (The leftmost byte is number 1). 
 6507  Where will the radix point be, in registers A 
 6516  and X, after the instructions|'{A9}|∂!!!!!!!!!!!!!!!!!!!|6|∂
 6521  !!!!!!!!!!!!!!!!!!!|6|∂|E|;|>!!|2a)!|¬l|¬d|¬a!|¬a|'
 6524  !!|2b)!!|¬l|¬d|¬a!|9|3|¬a|'>|>!!|2|9|6!!|¬m|¬u|¬l!|¬b?|'
 6528  !!|2|9|7!!|¬s|¬r|¬a|¬x!|¬5?|'>|>|;!!|2|9|7!!|¬d|¬i|¬v!|¬b|'
 6533  >{A9}|9|1|≡5|≡.|9|4[|*/|↔c|↔c|\] Explain why a 
 6538  negative integer in nines' complement notation 
 6544  has a representation in ten's complement notation 
 6551  that is always one greater, if the representations 
 6559  are regarded as positive.|'|Hβ{U0}{H10L12M29}|π58320#Compute
folio 254 galley 6
 6563  r Programming!(Knuth/Addison-Wesley)!f. 254!ch. 
 6566  4!g. 6|'{A6}{H9L11}|9|1|≡6|≡.|9|4[|*/|↔O|↔o|\] 
 6569  What are the largest and smallest |εp-|πbit integers 
 6577  that can be represented in (a) signed-magnitude 
 6584  binary notation, (b) two's complement notation, 
 6590  (c) ones' complement notation?|'{A3}|9|1|≡7|≡.|9|4[|εM|π|*/|↔
 6594  P|↔c|\] The text de_nes ten's complement notation 
 6601  only for integers represented in a single computer 
 6609  word. Is there a way to de_ne a ten's complement 
 6619  notation |εfor all real numbers, |πhaving ``in_nite 
 6626  precision,'' analogous to the text's de_nition? 
 6632  Is there a similar way to de_ne a nines' complement 
 6642  notation for all real numbers?|'{A3}|9|1|≡8|≡.|9|4[|εM|π|*/|↔
 6647  O|↔c|\] Prove Eq. (5).|'{A3}|9|1|≡9|≡.|9|4[|*/|↔O|↔C|\] 
 6652  Change the following |εoctal |πnumbers to |εhexadecimal 
 6659  |πnotation, using the hexadecimal digits |¬0, 
 6665  |¬1,|4.|4.|4.|4, |¬f|¬. |*/|↔O|↔P|≤⊃ |↔C|↔o|↔C|↔C|≤⊃ 
 6669  |↔P|↔C|↔C|↔c|↔P|↔p|↔o|≤⊃ |↔p|↔o|↔C|↔M|↔C|↔L|↔L|↔o|≤⊃ 
 6671  |↔L|↔p|↔P|↔o|↔p|↔C|↔C.|\|'{A3}|≡1|≡0|≡.|9|4[|εM|π|*/|↔P|↔P|\]
 6672   Generalize Eq. (5) to mixed radix notation.|'
 6680  {A3}|≡1|≡1|≡.|9|4[|*/|↔P|↔P|\] Give an algorithm 
 6684  which computes the sum of |ε(a|βn|4.|4.|4.|4a|β1a|β0)|βα_↓|β
 6689  2 |πand |ε(b|βn|4.|4.|4.|4b|β1b|β0)|βα_↓|β2, 
 6692  |πusing the |→α_↓2 number system, obtaining the 
 6699  answer |ε(c|βn|βα+↓|β2|4.|4.|4.|4c|β1c|β0)|βα_↓|β2.|'
 6701  {A3}|π|≡1|≡2|≡.|9|4[|*/|↔P|↔L|\] Give algorithms 
 6704  to convert (a) the binary signed magnitude number 
 6712  |→|¬N|ε(a|βn|4.|4.|4.|4a|β0)|β2 |πto its negative 
 6716  binary form |ε(b|βn|βα+↓|β1|4.|4.|4.|4b|β0)|βα_↓|β2; 
 6719  |πand (b) the negative binary number |ε(b|βn|βα+↓|β1|4.|4.|4
 6725  .|4b|β0)|βα_↓|β2 |πto its signed magnitude form 
 6731  |→|¬N(a|βn|βα+↓|β1|4.|4.|4.|4a|β0)|β2.|'{A3}|≡1|≡3|≡.|9|4[|ε
 6732  M|π|*/|↔P|↔O|\] In the decimal system there are 
 6739  some numbers with two in_nite decimal expansions, 
 6746  e.g., 2.3599999|4|¬O|4|¬O|4|¬O|4α=↓|42.3600000|4.|4.|4. 
 6748  Does the |εnegative decimal |π(base |→α_↓10) 
 6754  system have unique expansions, or are there real 
 6762  numbers with two di=erent in_nite expansions 
 6768  in the base also?|'{A3}|≡1|≡4|≡.|9|4[|*/|↔O|↔M|\] 
 6773  Multiply (11321)|β2|ε|βi |πby itself in the quater-imaginary
 6779   system using the method illustrated in the text.|'
 6788  {A3}|≡1|≡5|≡.|9|4[|εM|π|*/|↔P|↔M|\] What are the 
 6792  sets |εS|4α=↓|4|¬T|¬K|βk|β|¬R|β1|4a|βkb|gα_↓|gk|4|¬G|4a|βk 
 6794  |πan allowable digit|¬Y, analogous to Fig. 1, 
 6801  for the negative decimal and for the quater-imaginary 
 6809  number systems?|'{A3}|≡1|≡6|≡.|9|4[|εM|π|*/|↔P|↔M|\] 
 6812  Design an algorithm to add 1 to |ε(a|βn|4.|4.|4.|4a|β1a|β0)|
 6819  βi|βα_↓|β1 |πin the |εi|4α_↓|41 |πnumber system.|'
 6825  {A3}|≡1|≡7|≡.|9|4[|εM|π|*/|↔L|↔c|\] It may seem 
 6829  peculiar that the number |εi|4α_↓|41 |πhas been 
 6836  given as a number-system base, instead of the 
 6844  similar but simpler number |εi|4α+↓|41. |πCan 
 6850  every complex number |εa|4α+↓|4bi, |πwhere |εa 
 6856  |πand |εb |πare integers, be represented in a 
 6864  positional number system to base |εi|4α+↓|41, 
 6870  |πusing only the digits 0 and 1?|'{A3}|≡1|≡8|≡.|9|4[|εHM|π|*/
 6877  |↔L|↔P|\] Show that the set |εS |πof Fig. 1 is 
 6887  a closed set which contains a neighborhood of 
 6895  the origin. (Consequently, every complex number 
 6901  has a ``binary'' representation to base |εi|4α_↓|41.)|'
 6908  {A3}|π|≡1|≡9|≡.|9|4[|*/|↔P|↔L|\] (David W. Matula.) 
 6912  Let |εD |πbe a set of |εb |πintegers, containing 
 6921  exactly one solution to the congruence |εx|4|"o|4j 
 6928  |π(modulo |εb) |πfor |ε0|4|¬E|4j|4|¬W|4b. |πProve 
 6933  that all integers |εm |π(positive, negative, 
 6939  or zero) can be represented in the form |εm|4α=↓|4(a|βn|4.|4
 6947  .|4.|4a|β0)|βb, |πwhere all the |εa|βj |πare 
 6953  in |εD, |πif and only if all integers in the 
 6963  range |ε|λ3|4|¬E|4m|4|¬E|4u |πcan be represented, 
 6968  where |ε|λ3|4α=↓|4|→α_↓|πmax|¬T|εa|4|¬G|4a|4|¬A|4D|¬Y/(b|4α_
 6969  ↓|41), u|4α=↓|4|→α_↓|πmin|ε|¬Ta|4|¬G|4a|4|¬A|4D|¬Y|¬Y/(b|4α_
 6970  ↓|41). |πFor example, |εD|4α=↓|4|¬T|→α_↓1,|40,|4.|4.|4.|4,|4
 6973  b|4α_↓|42|¬Y |πsatis_es the conditions for all 
 6979  |εb|4|¬R|43. [Hint|*/:|\ |πDesign an algorithm 
 6984  which constructs a suitable representation.]|'
 6989  {A3}|≡2|≡0|≡.|9|4[|εHM|π|*/|↔P|↔l|\] (David W. 
 6992  Matula.) Consider a decimal number system which 
 6999  uses the digits |εD|4α=↓|4|¬T|→α_↓1, 0, 8, 17, 
 7006  26, 35, 44, 53, 62, 71|¬Y |πinstead of |¬T|ε0, 
 7015  1,|4.|4.|4.|4,|49|¬Y. |πThe result of exercise 
 7020  19 implies (as in exercise 18) that all real 
 7029  numbers have an in_nite decimal expansion using 
 7036  digits from |εD.|'|π!|9|7|4In the usual decimal 
 7043  system, some numbers have two representations 
 7049  (cf. exercise 13). (a) find a real number which 
 7058  has |εmore |πthan two |εD-|πdecimal representations. 
 7064  (b) Show that no real number has in_nitely many 
 7073  |εD-|πdecimal representations. (c) Show that 
 7078  uncountably many numbers have two or more |εD-|πdecimal 
 7086  representations.|'|≡2|≡1|≡.|9|4[|εM|π|*/|↔P|↔P|\] 
 7088  (C. E. Shannon.) Can every real number (positive, 
 7096  negative, or zero) be expressed in a ``balanced-decimal'' 
 7104  system, i.e., in the form |ε|¬K|βk|β|¬E|βn|4a|βk10|gk, 
 7110  |πfor some integer |εn |πand some sequence |εa|βn, 
 7118  a|βn|βα_↓|β1, a|βn|βα_↓|β2, .|4.|4.|4, |πwhere 
 7122  each |εa|βk |πis one of the ten numbers |¬T|→α_↓4|f1|d32|), 
 7131  |→α_↓3|f1|d32|), |→α_↓2|f1|d32|), |→α_↓1|f1|d32|), 
 7134  |→α_↓|f1|d32|), |f1|d32|), 1|f1|d32|), 2|f1|d32|), 
 7138  3|f1|d32|), 4|f1|d32|)|¬Y? (Note that zero is 
 7144  not one of the allowed digits, but we implicitly 
 7153  assume that |εa|βn|βα+↓|β1, a|βn|βα+↓|β2, .|4.|4. 
 7158  |πare zero.) Find all representations of zero 
 7165  in this number system, and _nd all representations 
 7173  of unity.|'{A3}|≡2|≡2|≡.|9|4[|εHM|π|*/|↔P|↔C|\] 
 7176  Let |ε|≤a|4α=↓|4|→α_↓|¬K|βm|β|¬R|β1|410|gα_↓|gm|i2. 
 7178  |πGiven |ε|≤|≤o|4|¬Q|40 |πand any real number 
 7184  |εx, |πprove that there is a ``decimal'' representation 
 7192  such that 0|4|¬W|4|¬G|εx|4α_↓|4|¬K|β0|β|¬E|βk|β|¬E|βn|4a|βk1
 7194  0|gk|¬G|4|¬W|4|≤o, |πwhere each |εa|βk |πis allowed 
 7200  to be only one of the three values 0, 1, or |ε|≤a. 
 7212  |π(Note that no negative powers of 10 are used 
 7221  in this representation*3)|'{A3}|≡2|≡3|≡.|9|4[|εHM|π|*/|↔L|↔c|\
 7224  ] Let |εD |πbe a set of |εb |πreal numbers such 
 7235  that every positive real number has a representation 
 7243  |ε|¬K|βk|β|¬E|βn|4a|βk|=∩b|gk |πwith all |εa|βk|4|¬A|4D. 
 7247  |πExercise 20 shows that there may be many numbers 
 7256  without |εunique |πrepresentations; but prove 
 7261  that the set |εT |πof all such numbers has measure 
 7271  zero.|'{A3}|≡2|≡4|≡.|9|4[|*/|↔L|↔C|\] Find in_nitely 
 7275  many di=erent sets |εD |πof ten nonnegative integers 
 7283  satisfying the following three conditions: (i) 
 7289  gcd(|εD)|4α=↓|41; |π(ii) 0|4|¬A|4|εD; |π(iii) 
 7293  every positive real number can be represented 
 7300  in the form |ε|¬K|βk|β|¬E|βn|4a|βk10|gk |πwith 
 7305  all |εa|βk|4|¬A|4D.|'{A3}|π|≡2|≡5|≡.|9|4[|εM|π|*/|↔P|↔C|\] 
 7308  (S. A. Cook.) Let |εb, u, |πand |εv |πbe positive 
 7318  integers, where |εb|4|¬R|4|π2 and 0|4|¬W|4|εv|4|¬W|4b|gm. 
 7323  |πShow that the base |εb |πrepresentation of 
 7330  |εu/v |πdoes not contain a run of |εm |πconsecutive 
 7339  digits equal to |εb|4α_↓|41 |πto the right of 
 7347  the radix point. (By convention, no runs of in_nitely 
 7356  many |ε(b|4α_↓|41)|π's are permitted in the standard 
 7363  base |εb |πrepresentation.)|'{A3}|≡2|≡6|≡.|9|4[|εHM|π|*/|↔L|↔
 7366  c|\] (N. S. Mendelsohn.) Let |ε|↔b|≤b|βn|↔v |πbe 
 7373  a sequence of real numbers de_ned for all integers 
 7382  |εn, |→α_↓|¬X|4|¬W|4n|4|¬W|4|¬X, |πsuch that|'
 7386  {A3}|ε|≤b|βn|4|¬Q|4|≤b|βn|βα+↓|β1;!!|π|uwlim|uc|)|.|εn|¬M|¬X
 7386  |)|4|≤b|βn|4α=↓|4|¬X;!!|π|uwlim|uc|)|.|εn|¬M|→α_↓|¬X|)|4|≤b|
 7386  βn|4α=↓|40.|;{A9}|πLet |ε|↔bc|βn|↔v |πbe an arbitrary 
 7392  sequence of positive integers, de_ned for all 
 7399  integers |εn, |→α_↓|¬X|4|¬W|4n|4|¬W|4|¬X. |πLet 
 7403  us say that a number |εx |πhas a ``generalized 
 7412  representation'' if there is an integer |εn |πand 
 7420  a sequence of integers |εa|βn, a|βn|βα_↓|β1, 
 7426  a|βn|βα_↓|β2, . . . |πsuch that |εx|4α=↓|4|¬K|βk|β|¬E|βn|4a|
 7432  βk|≤b|βk, |πwhere |εa|βn|4|=|↔6α=↓|40, 0|4|¬E|4a|βk|4|¬E|4c|
 7435  βk, |πand |εa|βk|4|¬W|4c|βk |πfor in_nitely many 
 7441  |εk.|'|π!|9|9|2Show that every positive real 
 7447  number |εx |πhas exactly one generalized representation 
 7454  if and only if |ε|≤b|βn|βα+↓|β1|4α=↓|4|¬K|βk|β|¬E|βn|4c|βk|≤
 7458  b|βk |πfor all |εn. |π(Consequently, the mixed 
 7465  radix systems with integer bases have this property; 
 7473  and the mixed radix systems with |ε|≤b|β1|4α=↓|4(c|β0|4α+↓|4
 7479  1)|≤b|β0, |≤b|β2|4α=↓|4(c|β1|4α+↓|41)(c|β0|4α+↓|41)|≤b|β0, 
 7481  . . . , |≤b|βα_↓|β1|4α=↓|4|≤b|β0/(c|βα_↓|β1|4α+↓|41), 
 7486  . . . |πare the most general number systems of 
 7496  this type.)|'{A3}|≡2|≡7|≡.|9|4[|εM|π|*/|↔P|↔O|\] 
 7499  Show that every nonzero integer has a unique 
 7507  ``reversing binary representation'' |ε2|ge|r0|4α_↓|42|ge|r1|
 7510  4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4(|→α_↓1)|gk2|ge|rk 
 7511  |πwhere |εe|β0|4|¬W|4e|β1|4|¬W|4|¬O|4|¬O|4|¬O|4|¬W|4e|βk.|'
 7513  {A3}|π|≡2|≡8|≡.|9|4[|εM|π|*/|↔P|↔M|\] Show that 
 7516  every nonzero complex number of the form |εa|4α+↓|4bi 
 7524  |πwhere |εa |πand |εb |πare integers has a unique 
 7533  ``revolving binary representation''|'{A9}|ε(1|4α+↓|4i)|ge|r0
 7536  |4α+↓|4i(1|4α+↓|4i)|ge|r1|4α_↓|4(1|4α+↓|4i)|ge|r2|4α_↓|4i(1|
 7536  4α+↓|4i)|ge|r3|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4i|gk(1|4α+↓|4i)|ge|
 7536  rk,|;{A9}|πwhere |εe|β0|4|¬W|4e|β1|4|¬W|4|¬O|4|¬O|4|¬O|4|¬W|
 7538  4e|βk. |π(Cf. exercise 27.)|'{A3}|≡2|≡9|≡.|9|4[|εM|π|*/|↔L|↔C
 7542  |\] (N. G. de Bruijn.) Let |εS|β0, S|β1, S|β2, 
 7551  . . . |πbe sets of nonnegative integers; we will 
 7561  say that the collection |εS|β0, S|β1, S|β2, . 
 7569  . . |πhas Property B if every nonnegative integer 
 7578  |εn |πcan be written in the form|'{A9}|εn|4α=↓|4s|β0|4α+↓|4s
 7585  |β1|4α+↓|4s|β2|4α+↓|4|¬O|4|¬O|4|¬O|4,!!s|βj|4|¬A|4S|βj|;
 7586  {A9}|πin exactly one way. (Property B implies 
 7593  that 0|4|¬A|4|εS|βj |πfor all |εj, |πsince |εn|4α=↓|40 
 7600  |πcan only be represented as 0|4α+↓|40|4α+↓|40|4α+↓|4|¬O|4|¬
 7605  O|4|¬O|4.) Any mixed radix number system with 
 7612  radices |εb|β0, b|β1, b|β2, . . . |πprovides 
 7620  an example of sets satisfying Property B, if 
 7628  we let |εS|βj|4α=↓|4|¬T0,|4q|βj, .|4.|4.|4, (b|βj|4α_↓|41)q|
 7632  βj|¬Y, |πwhere |εq|βj|4α=↓|4b|β0b|β1|4.|4.|4.|4b|βj|βα_↓|β1;
 7634   |πhere the representation of |εn|4α=↓|4s|β0|4α+↓|4s|β1|4α+↓
 7639  |4s|β2|4α+↓|4.|4.|4. |πcorresponds in an obvious 
 7644  manner to its mixed radix representation (9). 
 7651  Furthermore, if |εS|β0, S|β1, S|β2, . . . |πhas 
 7660  Property B, and if |εA|β0, A|β1, A|β2, . . . 
 7670  |πis any partition of the nonnegative integers 
 7677  (so that |εA|β0|4|↔q|4A|β1|4|↔q|4A|β2|4|↔q|4|¬O|4|¬O|4|¬O|4α
 7679  =↓|4|¬T0, 1, 2, . . .|¬Y |πand |εA|βi|4|↔Q|4A|βj|4α=↓|40 
 7687  |πfor |εi|4|=|↔6α=↓|4j; |πsome |εA|βj|π's may 
 7692  be empty), then the ``collapsed'' collection 
 7698  |εT|β0, T|β1, T|β2, . . . |πalso has Property 
 7707  B, where |εT|βj |πis the set of all sums |ε|¬K|βi|β|¬A|βA|mj
 7716  |4s|βi |πtaken over all possible choices of |εs|βi|4|¬A|4S|β
 7723  i.|'|π!|9|9|2Prove that |εany |πcollection |εT|β0, 
 7729  T|β1, T|β2, . . . |πwhich satis_es Property B 
 7738  may be obtained by collapsing some collection 
 7745  |εS|β0, S|β1, S|β2, . . . |πthat corresponds 
 7753  to a mixed radix number system.|'{A3}|≡3|≡0|≡.|9|4[|εM|π|*/|↔
 7759  L|↔m|\] (N. G. de Bruijn.) The radix |→α_↓2 number 
 7768  system shows us that every integer (positive, 
 7775  negative, or zero) has a unique representation 
 7782  of the form|'{A9}(|→α_↓2)|ε|ge|r1|4α+↓|4(|→α_↓2)|ge|r2|4α+↓|
 7785  4|¬O|4|¬O|4|¬O|4α+↓|4(|→α_↓2)q|ge|rt,!!e|β1|4|¬Q|4e|β2|4|¬Q|
 7785  4|¬O|4|¬O|4|¬O|4|¬Q|4e|βt|4|¬R|40,!!t|4|¬R|40.|;
 7786  {A9}|πThe purpose of this exercise is to explore 
 7794  generalizations of this phenomenon.|'{I1.7H}|9|5a)|9Let 
 7799  |εb|β0, b|β1, b|β2, . . . |πbe a sequence of 
 7809  integers such that every integer |εn |πhas a 
 7817  unique representation of the form|'{A9}!!|2|εn|4α=↓|4b|βe|m1
 7822  |4α+↓|4b|βe|m2|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4b|βe|mt,!!e|β1|4|¬Q
 7822  |4e|β2|4|¬Q|4|¬O|4|¬O|4|¬O|4|¬Q|4e|βt|4|¬R|40,!!t|4|¬R|40.|;
 7823  {A9}|π!!|2(Such a sequence |ε|↔bb|βn|↔v |πis 
 7828  called a ``binary basis.'') Show that there is 
 7836  an index |εj |πsuch that |εb|βj |πis odd, but 
 7845  |εb|βk |πis even for all |εk|4|=|↔6α=↓|4j.|'|9|4|πb)|9Prove 
 7852  that a binary basis |ε|↔bb|βn|↔v |πcan always 
 7859  be rearranged into the form |εd|β0, 2d|β1, 4d|β2, 
 7867  . . .|4α=↓|4|↔b2|gnd|βn|↔v, |πwhere each |εd|βk 
 7873  |πis odd.|'|9|6c)|9If each of |εd|β0, d|β1, d|β2, 
 7881  . . . |πin (b) is |→|¬N1, prove that |ε|↔bb|βn|↔v 
 7891  |πis a binary basis if and only if there are 
 7901  in_nitely many |→α+↓1's and in_nitely many |→α_↓1's.|'
 7908  |9|4d)|9Prove that 7, |→α_↓13|4|¬O|42, 7|4|¬O|42|g2, 
 7913  |→α_↓13|4|¬O|42|g3,|4.|4.|4.|4,|47|4|¬O|42|g2|ε|gk, 
 7914  |→α_↓13|4|¬O|42|g2|gk|gα+↓|g1,|4.|4.|4. |πis 
 7916  a binary basis, and _nd the representation of 
 7924  |εn|4α=↓|41.|'{IC}{A3}|π|≡3|≡1|≡.|9|4[|εM|π|*/|↔L|↔C|\] 
 7926  A generalization of two's complement arithmetic, 
 7932  called ``2-adic numbers,'' was invented about 
 7938  1900 by K. Hensel. (In fact he treated |εp-adic 
 7947  numbers, |πfor any prime |εp.) |πA 2-adic number 
 7955  may be regarded as a binary number|'{A9}|εu|4α=↓|4(.|4.|4.|4
 7962  u|β3u|β2u|β1u|β0.u|βα_↓|β1|4.|4.|4.|4u|βα_↓|βn)|β2,|;
 7963  {A9}|πwhose representation extends in_nitely 
 7967  far to the left, byt only _nitely many places 
 7976  to the right, of the binary point. Addition, 
 7984  subtraction, and multiplication of 2-adic numbers 
 7990  is done according to the ordinary procedures 
 7997  of arithmetic, which can in principle be extended 
 8005  inde_nitely to the left. For example,|'{A9}|9|77|4|∂α=↓|4(.|
 8011  4.|4.|4000000000000111)|β2!|7!!!|9|7|f1|d37|)|4|∂α=↓|4(.|4.|
 8011  4.|4110110110110111)|β2|9|6|;| |→α_↓7|4|Lα=↓|4(.|4.|4.|41111
 8012  11111111001)|β2| |→α_↓|f1|d37|)|4|Lα=↓|4(.|4.|4.|40010010010
 8012  01001)|β2>| |f7|d34|)|4|Lα=↓|4(.|4.|4.|4000000000000001.11)|
 8013  β2| |f1|d310|)|4|Lα=↓|4(.|4.|4.|4110011001100110.1)|β2>
 8014  {H10}|¬H{H9}|v4|→α_↓7|4α=↓|4(.|4.|4.|4100000010110101)|β2 
 8015  or (.|4.|4.|4011111101001011)|β2.|;|Hβ*?*?*?*?{U0}{H10L12M29}|π5
folio 259 galley 7
 8017  8320#Computer Programming!(Knuth/Addison-Wesley)!f. 
 8019  259!ch. 4!g. 7|'{A6}{H9L11}Here 7 is the ordinary 
 8027  binary integer seven, while |→α_↓7 is its two's 
 8035  complement (extending in_nitely to the left); 
 8041  it is easy to verify that the ordinary procedure 
 8050  for addition of binary numbers will give |→α_↓7|4α+↓|47|4α=↓
 8057  |4(.|4.|4.|400000)|β2|4α=↓|40, when the procedure 
 8061  is continued inde_nitely. The values of |f1|d37|) 
 8068  and |→α_↓|f1|d37|) are the unique 2-adic numbers 
 8075  which, when formally multiplied by 7, give 1 
 8083  and |→α_↓1, respectively. The values of |f7|d34|) 
 8090  and |f1|d310|) are examples of 2-adic numbers 
 8097  which are not 2-adic ``integers,'' since they 
 8104  have nonzero bits to the right of the binary 
 8113  point. The two values of {H11}|¬H{H10}|v4|→α_↓7|), 
 8119  which are negatives of each other, are the two 
 8128  2-adic numbers which, when formally squared, 
 8134  yield the value (.|4.|4.|4111111111111001)|β2.|'
 8138  {I1.7H}|9|5a)|9Prove that any 2-adic number |εu 
 8144  |πcan be divided by any nonzero 2-adic number 
 8152  |εv |πto obtain a unique 2-adic number |εw |πsatisfying 
 8161  |εu|4α=↓|4vw. |π(Hence the set of 2-adic numbers 
 8168  forms a ``_eld''; cf. Section 4.6.1.)|'|9|4b)|9Prove 
 8175  that the 2-adic representation of the rational 
 8182  number |→α_↓1/(|ε2n|4α+↓|41) |πmay be obtained 
 8187  as follows, when |εn |πis a positive integer: 
 8195  First _nd the ordinary binary expansion of 1/(2|εn|4α+↓|41),
 8202   |πwhich has the periodic form (0.|ε|≤a|≤a|≤a|4.|4.|4.)|β2 
 8209  |πfor some string |ε|≤a |πof 0's and 1's. Then 
 8218  |→α_↓1/|ε(2n|4α+↓|41) |πis the 2-adic number 
 8223  (.|4.|4.|4|ε|≤a|≤a|≤a)|β2.|'|π|9|6c)|9Prove that 
 8226  the representation of a 2-adic number |εu |πis 
 8234  periodic (that is, |βu|βN|βα+↓|β|≤l|4α=↓|4u|βN 
 8238  |πfor all large |εN, |πfor some |ε|≤l|4|¬R|41) 
 8245  |πif and only if |εu |πis rational (that is, 
 8254  |εu|4α=↓|4m/n, |πfor some integers |εm |πand 
 8260  |εn).|'|π|9|4d)|9Prove that, when |εn |πis an 
 8267  integer, {H11}|¬H{H10}|v4|εn|) |πis a 2-adic 
 8272  number if and only if |εn|4|πmod|42|ε|g2|gk|gα+↓|g3|4α=↓|42|
 8277  g2|gk |πfor some nonnegative integer |εk. |π(Thus, 
 8284  either |εn|4|πmod|48|4α=↓|41, or |εn|4|πmod|432|4α=↓|44, 
 8288  etc.)|'{A3}{IC}|≡3|≡2|≡.|9|4[|εM|π|*/|↔M|↔c|\] 
 8290  (I. Z. Ruzsa.) Prove that there are in_nitely 
 8298  many integers whose ternary representation uses 
 8304  only 0's and 1's and whose quinary representation 
 8312  uses only 0's, 1's, and 2's.|'{A25}{H10L12}|∨4|∨.|∨2|∨.|9|∨F
 8318  |∨L|∨O|∨A|∨T|∨I|∨N|∨G|∨-|∨P|∨O|∨I|∨N|∨T|9|∨A|∨R|∨I|∨T|∨H|∨M|
 8318  ∨E|∨T|∨I|∨C|'{A12}|∨4|∨.|∨2|∨.|∨1|∨.|9|∨S|∨i|∨n|∨g|∨l|∨e|∨-|
 8319  ∨P|∨r|∨e|∨c|∨i|∨s|∨i|∨o|∨n |∨C|∨a|∨l|∨c|∨u|∨l|∨a|∨t|∨i|∨o|∨n
 8320  |∨s|'{A6}In this section, we shall study the 
 8328  basic principles of doing arithmetic on ``⊗oating-point'' 
 8335  numbers, by analyzing the internal mechanism 
 8341  of such calculations. Perhaps many readers will 
 8348  have little interest in this subject, since their 
 8356  computers either have built-in ⊗oating-point 
 8361  instructions or therir computer manufacturer 
 8366  has supplied suitable subroutines. But, in fact, 
 8373  the material of this section should not merely 
 8381  be the concern of computer-design engineers or 
 8388  of a small clique of people who write library 
 8397  subroutines for new machines; |εevery |πwell-rounded 
 8403  programmer outht to have a knowledge of what 
 8411  goes on during the elementary steps of ⊗oating-point 
 8419  arithmetic. This subject is not at all as trivial 
 8428  as most people think; it involves a surprising 
 8436  amount of interesting information.|'{A12}|≡A|≡.|9|≡F|≡l|≡o|≡
 8440  a|≡t|≡i|≡n|≡g|≡-|≡p|≡o|≡i|≡n|≡t |≡n|≡o|≡t|≡a|≡t|≡i|≡o|≡n|≡.|
 8441  9|4We have discussed ``_xed-point'' notation 
 8446  for numbers in Section 4.1; in such a case the 
 8456  programmer knows where the radix point is assumed 
 8464  to lie in the numbers he manipulates. For many 
 8473  purposes it is considerably more convenient to 
 8480  let the position of the radix point be dynamically 
 8489  variable or ``⊗oating'' as a program is running, 
 8497  and to carry with each number an indication of 
 8506  the corresponding radix point position. This 
 8512  idea has been used for many years in scienti_c 
 8521  calculations, especially for expressing very 
 8526  large numbers like Avogadro's number |εN|4α=↓|46.02252|4α⊗↓|
 8531  410|g2|g3, or very small numbers like Planck's 
 8538  constant |εh|4α=↓|41.0545|4α⊗↓|410|gα_↓|g2|g7|4|πerg 
 8540  sec.|'!|9|7In this section we shall work with 
 8548  |εbase b, excess q, ⊃oating-point numbers with 
 8555  p digits|*/: |π|\Such a number is represented 
 8562  as two quantities |ε(e,|4f), |πand this notation 
 8569  stands for|'{A9}|ε(e,|4f)|4α=↓|4f|4α⊗↓|4b|ge|gα_↓|gq.|J!(1)|
 8571  ;{A9}|πHere |εe |πis an integer having a speci_ed 
 8580  range, and |εf |πis a signed fraction. We will 
 8589  adopt the convention that|'{A9}|ε|¬Gf|¬G|4|¬W|41;|;
 8594  {A9}|πin other words, the radix point appears 
 8601  at the left of the positional representation 
 8608  of |εf. |πMore precisely, the stipulation that 
 8615  we have |εp-|πdigit numbers means that |εb|gpf 
 8622  |πis an integer, and that|'{A9}|ε|→α_↓b|gp|4|¬W|4b|gpf|4|¬W|
 8627  4b|gp.|J!(2)|;{A9}|πThe term ``⊗oating binary'' 
 8632  implies that |εb|4α=↓|42, |π``⊗oating decimal'' 
 8637  implies |εb|4α=↓|410, |πetc. Using excess 50 
 8643  ⊗oating-decimal numbers with 8 digits, we can 
 8650  write, for example,|'{A9}|∂Avogadro's|6number|6|∂|εN|4|∂α=↓|
 8653  4(74,|4α+↓.60225200);|;{A4}|L|πPlanck's|6constant|L|εh|Lα=↓|
 8654  4(24,|4α+↓.10545000).>{A9}|π!|9|7The two components 
 8658  |εe |πand |εf |πof a ⊗oating-point number are 
 8666  called the |εexponent |πand the |εfraction |πparts, 
 8673  respectively. (Other names are occasionally used 
 8679  for this purpose, notably ``characteristic'' 
 8684  and ``mantissa''; but it is an abuse of terminology 
 8693  too call the fraction part a mantissa, since 
 8701  this concept has quite a di=erent meaning in 
 8709  connection with logarithms. Furthermore the English 
 8715  word mantissa means ``a worthless addition.'')|'
 8721  {A12}|≡B|≡.|9|≡N|≡o|≡r|≡m|≡a|≡l|≡i|≡z|≡e|≡d |≡c|≡a|≡l|≡c|≡u|
 8722  ≡l|≡a|≡t|≡i|≡o|≡n|≡s|≡.|9 A ⊗oating-point number 
 8726  |ε(e,|4f) |πis said to be |εnormalized |πif the 
 8734  most signi_cant digit of the representation of 
 8741  |εf |πis nonzero, so that|'{A9}|ε1/b|4|¬E|4|¬Gf|¬G|4|¬W|41;|
 8746  J!(5)|;{A9}|πor if |εf|4α=↓|40 |πand |εe |πhas 
 8753  its smallest possible value. It is possible to 
 8761  tell which of two normalized ⊗oating-point numbers 
 8768  has a greater magnitude by comparing the exponent 
 8776  parts _rst, and then testing the fraction parts 
 8784  only if the exponents areq equal.|'|Hβ*?*?*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
 8790